乐趣区

关于java:数据结构之链表

作者：

jiezi

在

链表

什么是链表

链表是一种真正动静的数据结构

数据存储在节点（Node）中。每一个元素都存储着下一个元素的节点，最初一个节点指向为NULL

长处：真正的动静，不须要解决固定容量的问题

毛病：丢失了随机拜访的能力

咱们能够由此实现一个根本的链表构造：

public class LinkedList<E> {
        private class Node{
            public E e;
            public Node next;
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
            public Node(E e) {
                this(e,null);
            }
            public Node() {
                this(null,null);
            }
            @Override
            public String toString() {
                return e.toString();
            }
        }
}

向链表中增加元素

头部插入元素

咱们应用一个head变量来存储第一个地位的元素。

如果咱们想增加666元素，咱们其实只须要让666的next存储head节点，而后让head指向666。

两头增加元素

如果咱们想在”1″的前面插入一个元素，应该怎么做？

咱们应用一个变量prev来存储”1″这个元素，咱们须要将要插入的数据的next指向prev的next，而后将prev的next来指向node就好了。

要害就是要找到增加的节点的前一个节点

public class LinkedList<E> {
        private class Node {
            public E e;
            public Node next;
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
            public Node(E e) {
                this(e, null);
            }
            public Node() {
                this(null, null);
            }
            @Override
            public String toString() {
                return e.toString();
            }
        }
        private Node head;
        private int size;
        public LinkedList() {
            head = null;
            size = 0;
        }
        //获取链表中元素的个数
        public int getSize() {
            return size;
        }
        //返回链表是否为空
        public boolean isEmpty() {
            return size == 0;
        }
        //在链表头增加新的元素
        public void addFirst(E e) {
            head = new Node(e, head);
            size++;
        }
        //在链表的index地位增加新的元素e
        //在链表中不是一个罕用的操作，练习应用
        public void add(int index, E e) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("Add failed. Illegal index.");
            }
            if (index == 0) {
                addFirst(e);
            } else {
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                prev.next = new Node(e, prev.next);
                size++;
            }
        }
        //向开端插入一个元素
        public void addLast(E e) {
            add(size, e);
        }
}

为链表设立虚构头结点

因为在两头插入咱们都要获取前一个节点，如果咱们在最后面插入就无奈获取上一个节点，由此咱们设立一个虚构头结点。这样的话所有的节点都有了前置节点。

public class LinkedList<E> {
        private class Node {
            public E e;
            public Node next;
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
            public Node(E e) {
                this(e, null);
            }
            public Node() {
                this(null, null);
            }
            @Override
            public String toString() {
                return e.toString();
            }
        }
        private Node dummyHead;
        private int size;
        public LinkedList() {
            dummyHead = new Node(null, null);
            size = 0;
        }
        //获取链表中元素的个数
        public int getSize() {
            return size;
        }
        //返回链表是否为空
        public boolean isEmpty() {
            return size == 0;
        }
        //在链表头增加新的元素
        public void addFirst(E e) {
            add(0,e);
        }
        //在链表的index地位增加新的元素e
        //在链表中不是一个罕用的操作，练习应用
        public void add(int index, E e) {
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("Add failed. Illegal index.");
            }
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            prev.next = new Node(e, prev.next);
            size++;
        }
        //向开端插入一个元素
        public void addLast(E e) {
            add(size, e);
        }
}

链表的遍历、批改和查问

    //获取某个地位的元素，在链表中不是一个罕用的操作，练习应用
    public E get(int index){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Illegal index.");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.e;
    }
    //取得第一个元素
    public E getFirst(){
        return get(0);
    }
    //取得最初一个元素
    public E getLast(){
        return get(size - 1);
    }
    //批改某个地位的元素，在链表中不是一个罕用的操作，练习应用
    public void set(int index,E e){
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed. Illegal index.");
        }
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.e = e;
    }
    //查找链表中是否有该元素e
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while (cur != null){
            if (cur.e.equals(e)){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        for(Node cur = dummyHead.next ; cur != null ; cur = cur.next) {
            res.append(cur + "->");
        }
        res.append("NULL");
        return res.toString();
    }

链表元素的删除

咱们如果想删除索引为2地位的元素，咱们还是须要先找到前一个节点。

prev.next就是要删除的元素，所以咱们须要将prev的next指向要删除的节点的next节点就好。

而后将delNode置为null即可。

    //删除某个地位的元素并返回，在链表中不是一个罕用的操作，练习应用
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Illegal index.");
        }
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size --;
        return delNode.e;
    }
    // 从链表中删除元素e
    public void removeElement(E e){
        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.e.equals(e)) {
                break;
            }
            prev = prev.next;
        }
        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }

链表的工夫复杂度剖析

  • 增加操作

    • addLast(e) O(n)
    • addFirst(e) O(1)
    • add(index,e) O(n)

  • 删除操作

    • removeLast(e) O(n)
    • removeFirst(e) O(1)
    • remove(index,e) O(n)

  • 批改操作

    • set(index,e) O(n)

  • 查找操作

    • get(index) O(n)
    • contains(e) O(n)

应用链表实现栈

因为咱们只操作队首的话，工夫复杂度都是O(1)，所以咱们正好能够应用链表来实现栈，这样性能会大大提高。

public class LinkedListStack<E> implements Stack<E> {
        private LinkedList<E> list;
        public LinkedListStack(){
            list = new LinkedList<>();
        }
        @Override
        public int getSize() {
            return list.getSize();
        }
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
        @Override
        public void push(E e) {
            list.addFirst(e);
        }
        @Override
        public E pop() {
            return list.remove(0);
        }
        @Override
        public E peek() {
            return list.getFirst();
        }
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Stack: top ");
            res.append(list);
            return res.toString();
        }
}

应用链表实现队列

咱们不要再应用dummyHead，因为咱们不须要操作两头元素，然而咱们要留神链表为空的状况。

public class LinkedListQueue<E> implements Queue<E> {
        private class Node {
            public E e;
            public Node next;
            public Node(E e, Node next) {
                this.e = e;
                this.next = next;
            }
            public Node(E e) {
                this(e, null);
            }
            public Node() {
                this(null, null);
            }
            @Override
            public String toString() {
                return e.toString();
            }
        }
        private Node head,tail;
        private int size;
        public LinkedListQueue(){
            head = null;
            tail = null;
            size = 0;
        }
        @Override
        public int getSize() {
            return size;
        }
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
        @Override
        public void enqueue(E e) {
            if (tail == null){
                tail = new Node(e);
                head = tail;
            }else{
                tail.next = new Node(e);
                tail = tail.next;
            }
            size ++;
        }
        @Override
        public E dequeue() {
            if (isEmpty()){
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
            Node retNode = head;
            head = retNode.next;
            retNode.next = null;
            if (head == null){
                tail = null;
            }
            size --;
            return retNode.e;
        }
        @Override
        public E getFront() {
            if (isEmpty()){
                throw new IllegalArgumentException("Queue is empty");
            }
            return head.e;
        }
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Queue: front ");
            Node cur = head;
            while(cur != null) {
                res.append(cur + "->");
                cur = cur.next;
            }
            res.append("NULL tail");
            return res.toString();
        }
}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章