03_链表

动态数组有个明显的缺点：
可能会造成内存空间的大量浪费
能否用到多少就申请多少内存？
链表可以办到这一点

初识链表

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

Snip20200914_7.png

Snip20200914_8.png

接口设计

链表的接口和动态数组是一致的

int size(){} // 元素的数量
boolean isEmpty(){} // 是否为空
void add(E element){} // 添加元素到最后面
void set(int index,E element){} // 设置index位置的元素
void add(int index,E element){} // 在index位置插入一个元素
void remove(int index){} // 删除index位置的元素
boolean contains(E element){} // 是否包含某个元素
E get(int index){} // 获取index位置的元素
int indexOf(E element){} // 查看元素的索引
void clear(){} // 清除所有元素

链表类型

依赖于指针

单向链表
单向循环链表
双向链表
双向循环链表

不依赖于指针 - 静态链表

有些编程语言是没有指针的，比如早期的BASIC、FORTRAN语言，那么在没有指针的情况下，如何实现链表？

静态链表，即通过数组模拟链表
数组的每个元素存放2个数据：值，下一个元素的索引，数组0位置存放的是头节点信息

Snip20200914_19.png

Snip20200914_20.png

如果数组的每一个元素只能存放1个数据，那么就使用2个数组，一个数组存放索引关系，一个数组存放值

代码实现

1. 单向链表

package LinkedList;

public class LZSingleLinkedList <E>{

    /**
     * 元素的数量
     */
    private int size;

    //第一个结点
    private Node<E> first;

    //结点元素
    private static class Node<E>{
        E element;
        Node<E> next;
        public  Node(E element,Node<E> next){
            this.element = element;
            this.next = next;
        }
    }

    /**
     * 元素找不到
     */
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        //插入数据
        if (index == 0){
            first = new Node(element,first);
        }else{
            Node<E> preNode = node (index-1);
            preNode.next = new Node<>(element,preNode.next);
        }
        size++;
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        first = null;
        size = 0;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);
        if (index == 0){
            first = first.next;
        }else {
            Node<E> preNode = node(index-1);
            preNode.next = preNode.next.next;
        }
        size--;
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        Node<E> node = node(index);
        node.element = element;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        Node<E> node = first;
        if (element == null){
            for (int i = 0;i<size;i++){
                if (node.element == null) return i;
                node = node.next;
            }
        }else{
            for (int i = 0;i<size;i++){
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0;i<index;i++){
            node = node.next;
        }
        return node;
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        Node<E> node = first;
        while (node != null){
            string.append(node.element);
            node = node.next;
            string.append(", ");
        }
        string.append("]");

        return string.toString();
    }

}

2. 单向链表增加虚拟头节点

有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟头节点（不存储数据）

Snip20200914_10.png

package LinkedList;

public class LZSingleLinkedList2 <E>{

    /**
     * 元素的数量
     */
    private int size;

    //第一个结点
    private Node<E> first;

    //结点元素
    private static class Node<E>{
        E element;
        Node<E> next;
        public Node(E element,Node<E> next){
            this.element = element;
            this.next = next;
        }
    }
    private  static final int ELEMENT_NOT_FOUND = -1;

    public LZSingleLinkedList2(){
        first = new Node(null,null);
    }

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        //插入数据
        Node<E> preNode = index == 0?first: node (index-1);
        preNode.next = new Node<>(element,preNode.next);
        size++;
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        first.next = null;
        size = 0;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);
        Node<E> preNode = index==0?first: node(index-1);
        preNode.next = preNode.next.next;
        size--;
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        Node<E> node = node(index);
        node.element = element;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        Node<E> node = first.next;
        if (element == null){
            for (int i = 0;i<size;i++){
                if (node.element == null) return i;
                node = node.next;
            }
        }else{
            for (int i = 0;i<size;i++){
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> node = first.next;
        for (int i = 0;i<index;i++){
            node = node.next;
        }
        return node;
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        Node<E> node = first.next;
        while (node != null){
            string.append(node.element);
            node = node.next;
            string.append(", ");
        }
        string.append("]");

        return string.toString();
    }

}

3. 双向链表

使用双向链表可以提升链表的综合性能

Snip20200914_12.png

当双向链表只有一个元素

Snip20200914_13.png

package LinkedList;

public class LZLinkedList <E>{

    /**
     * 元素的数量
     */
    private int size;

    /**
     * 第一个结点
     */
    private Node<E> first;

    /**
     * 最后一个结点
     */
    private Node<E> last;

    /**
     * 结点
     */
    private static class Node<E>{
        E element;
        Node<E> next;
        Node<E> prev;
        public  Node(E element,Node<E> prev,Node<E> next){
            this.element = element;
            this.next = next;
            this.prev = prev;
        }
    }
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        if(index == size) { //往最后面添加元素
            Node<E> oldLast = last;
            last = new Node<>(element, oldLast, null);
            if (oldLast == null) { //这是链表的第一个元素
                first = last;
            } else {
                oldLast.next = last;
            }
        }else{
            Node<E> next = node (index);
            Node<E> prev = next.prev;
            Node<E> node = new Node<>(element,prev,next);
            next.prev = node;
            if (prev == null){ // index == 0
                first = node;
            }else {
                prev.next = node;
            }
        }
        size++;
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        first = null;
        last = null;
        size = 0;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);

        Node<E> node = node(index);
        Node prev = node.prev;
        Node next = node.next;

        if (prev == null){
            first = next;
        }else {
            prev.next = next;
        }
        if (next == null){
            last = prev;
        }else {
            next.prev = prev;
        }

        size--;
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        Node<E> node = node(index);
        node.element = element;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        Node<E> node = first;
        if (element == null){
            for (int i = 0;i<size;i++){
                if (node.element == null) return i;
                node = node.next;
            }
        }else{
            for (int i = 0;i<size;i++){
                if (element.equals(node.element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    private Node<E> node(int index){
        rangeCheck(index);
        if (index>(size>>1)){ //从后向前找到节点
            Node<E> node = last;
            for (int i = size - 1;i >index ;i--){
                node = node.prev;
            }
            return node;
        }else { //从前向后找到节点
            Node<E> node = first;
            for (int i = 0;i<index;i++){
                node = node.next;
            }
            return node;
        }
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        Node<E> node = first;
        while (node != null && node.next != null){
            string.append(node.element).append("-").append(node.next.element).append(" , ");
            node = node.next;
        }

        string.append("]");
        return string.toString();
    }
}

4. 单向循环链表

Snip20200914_14.png

单向循环链表 - 只有1个节点

Snip20200914_15.png

package LinkedList;

public class LZSingleCircleLinkedList <E>{

    /**
     * 元素的数量
     */
    private int size;

    //第一个结点
    private Node<E> first;

    //结点元素
    private static class Node<E>{
        E element;
        Node<E> next;
        public  Node(E element,Node<E> next){
            this.element = element;
            this.next = next;
        }
    }
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        //插入数据
        if (index == 0){
            Node<E> node = new Node(element,first);
            Node<E> last = size == 0? node:node(size -1);
            first = node;
            last.next = node;
        }else{
            Node<E> preNode = node (index-1);
            preNode.next = new Node<>(element,preNode.next);
        }
        size++;
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        first = null;
        size = 0;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);
        if (index == 0){
            if (size == 1){ //数组中只有一个元素
                first = null;
            }else {
                first = first.next;
                node(size - 1).next = first;
            }
        }else {
            Node<E> preNode = node(index-1);
            preNode.next = preNode.next.next;
        }
        size--;
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        Node<E> node = node(index);
        node.element = element;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        Node<E> node = first;
        if (element == null){
            for (int i = 0;i<size;i++){
                if (node.element == null) return i;
                node = first.next;
            }
        }else{
            for (int i = 0;i<size;i++){
                if (element.equals(node.element)) return i;
                node = first.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> preNode = first;
        for (int i = 0;i<index;i++){
            preNode = preNode.next;
        }
        return preNode;
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        Node<E> node = first;
       do{
            string.append(node.element);
            node = node.next;
            string.append(", ");
        }while (node != first);

        string.append("]");

        return string.toString();
    }
}

5. 双向循环链表

Snip20200914_16.png

双向循环链表 - 只有一个节点

Snip20200914_17.png

package LinkedList;

public class LZCircleLinkedList <E>{

    /**
     * 元素的数量
     */
    private int size;

    /**
     * 第一个结点
     */
    private Node<E> first;

    /**
     * 最后一个结点
     */
    private Node<E> last;

    /**
     * 结点
     */
    private static class Node<E>{
        E element;
        Node<E> next;
        Node<E> prev;
        public  Node(E element,Node<E> prev,Node<E> next){
            this.element = element;
            this.next = next;
            this.prev = prev;
        }
    }
    private  static final int ELEMENT_NOT_FOUND = -1;

    /**
     * 添加元素到尾部
     * @param element
     */
    public void add(E element){
        add(size,element);
    }

    /**
     * 在index位置插入一个元素
     * @param index
     * @param element
     */
    public void add(int index,E element){
        if (index<0 || index>size) {
            outOfBounds(index);
        }

        if(index == size) { //往最后面添加元素
            Node<E> oldLast = last;
            Node<E> node = new Node<>(element, oldLast, first);
            if (oldLast == null) { //这是链表的第一个元素
                node.prev = node.next = last = first = node;
//                first = last;
//                first.next = first;
//                first.prev = first;
//                first = node;
//                last = node;
//                node.next = node;
//                node.prev = node;
            } else {
                last = node;
                oldLast.next = node;
                first.prev = node;
            }
        }else{
            Node<E> next = node (index);
            Node<E> prev = next.prev;
            Node<E> node = new Node<>(element,prev,next);
            next.prev = node;
            prev.next = node;
            if (prev == last){ // index == 0
                first = node;
            }
        }
        size++;
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        first = null;
        last = null;
        size = 0;
    }

    /**
     * 删除index位置的元素
     * @param index
     */
    public void remove(int index){
        rangeCheck(index);

        if (size == 1){
            first = last = null;
        }else {
            Node<E> node = node(index);
            Node prev = node.prev;
            Node next = node.next;
            prev.next = node.next;
            next.prev = node.prev;

            if (node == first){ //如果删除的是第一个元素
                first = next;
            }

            if (node == last){ //如果删除的是最后一个元素
                last = prev;
            }
        }
        size--;
    }

    /**
     * 设置index位置的元素
     * @param index
     * @param element
     */
    public void set(int index,E element){
        rangeCheck(index);
        Node<E> node = node(index);
        node.element = element;
    }

    /**
     * 元素的数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return  size == 0;
    }

    /**
     * 获取index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        rangeCheck(index);
        return node(index).element;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element){
        return indexOf(element) != ELEMENT_NOT_FOUND;
    }

    /**
     * 查看元素的索引
     * @param element
     * @return
     */
    public int indexOf(E element){
        Node<E> node = first;
        if (element == null){
            for (int i = 0;i<size;i++){
                if (node.element == null) return i;
                node = first.next;
            }
        }else{
            for (int i = 0;i<size;i++){
                if (element.equals(node.element)) return i;
                node = first.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    private Node<E> node(int index){
        rangeCheck(index);
        if (index>(size>>1)){ //从后向前找到节点
            Node<E> node = last;
            for (int i = size - 1;i >index ;i--){
                node = node.prev;
            }
            return node;
        }else { //从前向后找到节点
            Node<E> node = first;
            for (int i = 0;i<index;i++){
                node = node.next;
            }
            return node;
        }
    }

    /**
     * 检查下标越界
     * @param index
     * @return
     */
    private void rangeCheck(int index){
        if (index<0 || index >= size){
            outOfBounds(index);
        }
    }
    /**
     * 检查到下标越界，抛出异常
     * @param index
     * @return
     */
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("Index:"+index+"Size:"+size);
    }

    @Override
    public String toString(){
        StringBuffer string = new StringBuffer();
        string.append("size = ").append(size).append("\n[");
        Node<E> node = first;
        do {
            string.append(node.element).append("-").append(node.next.element).append(" , ");
            node = node.next;
        }while (node != first);

//        for (int i = 0; i < size; i++) {
//            if (i != 0) {
//                string.append(", ");
//            }
//            string.append(node.element);
//            node = node.next;
//        }

        string.append("]");
        return string.toString();
    }
}

如何发挥循环链表的最大威力

可以考虑增设1个成员变量、3个方法

current ：用于指向某个节点
void reset()：让current指向头节点first
E next()：让current往后走一步，也就是current = current.next
E remove()：删除current指向的节点，删除成功后让current指向下一个节点

Snip20200914_21.png

复杂度分析

添加
最好：O(1) 最坏：O(n) 平均：O(n)
添加元素到结尾
最好：O(1) 最坏：O(1) 平均：O(1)
删除
最好：O(1) 最坏：O(n) 平均：O(n)
设置index位置的值
最好：O(1) 最坏：O(n) 平均：O(n)
获取inde位置的值
最好：O(1) 最坏：O(n) 平均：O(n)

双向链表 vs 动态数组

复杂度对比

Snip20200914_22.png
动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容来解决）
双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存浪费
如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
如果频繁在头部进行添加、删除操作，建议选择使用双向链表（环形数组也可以）
如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
如果有频繁的查询操作（随机访问操作），建议选择使用动态数组