链表

什么是链表

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

数据存储在节点（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();}
}