第五章 链表

什么是链表？

动态数组有个明显缺点，可能造成内存空间的大量浪费。
能否实现用到多少内存就申请多少内存？链表可以实现这一点。
链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的（是物理存储单元非连续、非顺序的存储结构）。

单向链表

只有next指针。

    private static class Node<E> {
        E element;
        Node next;
        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
    }

查询

  /**
     * 获取指定index位置的前一个元素
     * 最好O(1)，获取第一个元素
     * 最坏O(n)，获取最后一个元素
     * 平均O(n)
     * @param element
     */
private Node getPreviousNode(int index) {
        Node prev = head;
        for (int i = 1; i < index; i++) {
            prev = prev.next;
        }
        return prev;
} 
public E get(int index) {
        rangCheck(index);
        if (index == 0) {
            return head.element;
        }
        Node prev = getPreviousNode(index);
        return (E) prev.next.element;
}

增加

/**
     * 最好O(1)，添加第一个元素
     * 最坏O(n)，添加最后一个元素
     * 平均O(n)
     * @param element
     */
public void add(int index, E element) {
        rangCheckForAdd(index);
        // 创建当前element节点 curNode
        // 找到 (index-1) 位置的节点 prev
        // 得到 index位置的节点(indexOldNode=prev.next)
        // 改变 prev.next 指向为新创建的curNode
        // curNode.next 指向 indexOldNode
        //index  0 1 2 3 4 5 6
        Node prev = getPreviousNode(index);
        prev.next = new Node(element, prev.next);
        size++;
    }

删除

/**
     * 最好O(1)，删除第一个元素
     * 最坏O(n)，删除最后一个元素
     * 平均O(n)
     * @param index
     * @return
     */ 
public E remove(int index) {
        rangCheck(index);
        if (index == 0) {
            E delValue = head.element;
            head = head.next;
            size--;
            return delValue;
        }
        Node prev = getPreviousNode(index);
        Node delNode = prev.next;
        E delValue = (E) delNode.element;
        prev.next = delNode.next;
        size--;
        return delValue;
}

设置

/**
     * 最好O(1)，设置第一个元素
     * 最坏O(n)，设置最后一个元素
     * 平均O(n)
     * @param index
     * @return
     */
public E set(int index, E element) {
        rangCheck(index);
        if (index == 0) {
            E oldValue = head.element;
            head = new Node(element, head.next);
            return oldValue;
        }
        Node prev = getPreviousNode(index);
        Node<E> indexNode = prev.next;
        prev.next = new Node(element, indexNode.next);
        return indexNode.element;
}

动态数组和链表的复杂度

资料上面说，链表的增加、删除的复杂度是O(1)，实际上是指增加、删除那一瞬间的操作（移动指针的动作是O(1)），但是在增删动作之前还是要寻找元素的位置，寻找的过程平均是O(n)，那么增加、删除整体完成就是O(n)。
**

双向链表

public class CustLinkedList<E> extends AbstractCustList<E> {
    private Node<E> head;
    private Node<E> tail;
    public CustLinkedList() {
    }
        private static class Node<E> {
        E element;
        Node prev;
        Node next;
        public Node(Node prev, E element, Node next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
    }
}

只有一个元素

查询

 public E get(int index) {
        if (index == 0) {
            return head.element;
        } else if (index == size - 1) {
            return tail.element;
        } else {
            return getNode(index).element;
        }
}
private Node<E> getNode(int index) {
        rangCheck(index);
        if (index < (size >> 1)) {
            //从头部开始查找
            return getNodeFormHead(index);
        } else {
            //从尾部查找
            return getNodeFormTail(index);
        }
 }
private Node<E> getNodeFormHead(int index) {
        // 0  1  2  3
        // 1->2->3->4
        //index=3 , i=0 ,node =2
        //index=3 , i=1 ,node =3
        //index=3 , i=2 ,node =4
        Node<E> node = head;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
}
private Node<E> getNodeFormTail(int index) {
        // 0  1  2  3
        // 1->2->3->4
        //index=1 , i=3 ,node =3
        //index=1 , i=2 ,node =2
        Node<E> node = tail;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
        return node;
}

添加

    public void add(E element) {
        addLast(element);
    }
    public void add(int index, E element) {
        rangCheckForAdd(index);
        if (index == 0) {
            addFirst(element);
        } else if (index == size) {
            addLast(element);
        } else {
            // 0  1  2  3
            // 1->2->3->4    在 index=2的位置插入 100
            // 1->2->100->3->4    在 index=2的位置插入 100
            // 找到原位置的节点
            Node<E> oldNode = getNode(index);
            Node prev = oldNode.prev;
            Node newNode = new Node(prev, element, oldNode);
            prev.next = newNode;
            oldNode.prev = newNode;
            size++;
        }
    }
    public void addFirst(E element) {
        Node first = head;
        Node<E> newNode = new Node<>(null, element, first);
        head = newNode;
        if (first == null) {
            tail = newNode;
        } else {
            first.prev = newNode;
        }
        size++;
    }
    public void addLast(E element) {
        Node last = tail;
        Node<E> newNode = new Node<>(last, element, null);
        tail = newNode;
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
    }

删除

public E remove(int index) {
        Node<E> oldNode = getNode(index);
        E element = oldNode.element;
        Node prev = oldNode.prev;
        Node next = oldNode.next;
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
            oldNode.prev = null;
        }
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
            oldNode.next = null;
        }
        oldNode.element = null;
        size--;
        return element;
    }

设置

    public E set(int index, E element) {
        Node<E> oldNode = getNode(index);
        oldNode.element = element;
        return oldNode.element;
    }

双向链表 VS 单向链表

双向链表 VS 动态数组

• 动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间的浪费（可以通过缩容来解决）。
• 双向链表：开辟、销毁内存空间的次数相对较多，但是不会造成内存空间的浪费。
• 如果频繁在尾部进行增加、删除操作，动态数组和双向链表都可以
• 如果频繁在头部进行添加、删除操作，建议使用双向链表
• 如果频繁在任意位置进行添加、删除操作，建议使用双向链表
• 如果频繁在任意位置进行查询，建议使用动态数组

有了双向链表，单向链表是否没用了？

• 并不是，在哈希表中使用的就是单向链表。

单向循环链表

只有一个节点

双向循环链表

只有一个节点

静态链表