526互联

第2章. 链表(LinkedList)

发布时间 2023-12-06 20:18:25作者: Ac_c0mpany丶

链表

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

单向链表

一、单向链表的设计

1.1、不带虚拟头结点

public class LinkedList<E> {
    // 链表的节点数量
    private int size;
    // 链表的头结点
    private Node<E> first;

    // 静态成员内部类:static静态的、因为是成员内部类所以可以用private修饰
    private static class Node<E>{
        // 节点自身存储的元素
        E element;
        // 保存下一个节点的地址
        Node<E> next;
		
        // 因为内部类也是一个类,所以也有构造方法
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
   // 不需要预先分配容量所以不需要写构造函数
}
1.2、带虚拟头结点

public class LinkedList<E> {
    // 链表的节点数量
    private int size;
    // 链表的头结点
    private Node<E> first;

    // 静态内部类
    private class Node<E>{
        // 节点自身存储的元素
        E element;
        // 保存下一个节点的地址
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
    // 带虚拟头节点的单链表
   	public LinkedList<E>() {
       first = new Node<E>(null, null);
   	}
}

二、链表的接口设计(学习其设计思想)

  • 左图：由于链表的大部分接口和动态数组一致，我们抽取出一个共同的List接口
  • 右图：由于链表和动态数组中有些方法的实现完全一样，我们将这些完全相同的方法放到一个抽象类中。这样ArrayList类和LinkedList类中实现完全一样的方法就在抽象类AbstractList中(抽象的父类,达到代码复用的目的)，而其他方法则声明在List接口中
// 动态数组和链表中都有且实现也完全一样的方法,我们抽取到AbstractList中
1、private void rangeCheck(int index)
2、private void rangeCheckForAdd(int index)
3、public int size()
4、public boolean isEmpty()
5、public boolean contains(E element)
6、public void add(E element)
2.1、List接口
package DataStructure._02链表;

public interface List<E> {
    /**
     * 接口是抽象方法(public abstract)和常量值(public static final)定义的集合。
     */

    // 常量值
    int ELEMENT_NOT_FOUND = -1;

    // 清除所有元素
    void clear();

    // 获取index位置的元素
    E get(int index);

    // 设置index位置的元素
    E set(int index, E element);

    // 在index位置插入一个元素
    void add(int index, E element);

    // 删除index位置的元素
    E remove(int index);

    // 查看元素的索引
    int indexOf(E element);
}
2.2、AbstractList类
package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-11-8:37
 */
public abstract class AbstractList<E> implements List<E> {
    // 元素的数量。
    // 声明为protected是为了给子类使用
    protected int size;

    protected void rangeCheck(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    protected void rangeCheckForAdd(int index) {
        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
        }
    }

    // 返回元素的数量
    public int size() {
        return size;
    }

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

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

    // 添加元素到末尾
    public void add(E element) {
        add(size, element);
    }
}
2.3、LinkedList类
package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-10-19:27
 */
public class LinkedList<E> extends AbstractList<E> implements List {

    // 链表的头结点
    private Node<E> first;

    // 静态内部类
    private class Node<E>{
        // 节点自身存储的元素
        E element;
        // 保存下一个节点的地址
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }
    
    @Override
    public void clear() {

    }

    @Override
    public E get(int index) {
        return null;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public void add(int index, E element) {

    }

    @Override
    public E remove(int index) {
        return null;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }
}
2.4、ArrayList类
package DataStructure._01动态数组;

import DataStructure._02链表.AbstractList;

/**
 * @author keyongkang
 * @date 2022-07-10-10:09
 */

public class ArrayList<E> extends AbstractList<E> implements List {

    // 动态数组的所有元素
    private E[] elements;

    // 动态数组的默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayList(int capacity) {
        capacity = (capacity < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capacity;
        elements = (E[])new Object[capacity];
    }

    public ArrayList() {
        //elements = new int[DEFAULT_CAPACITY];
        this(DEFAULT_CAPACITY);
    }

    // 添加元素到动态数组index索引位置
    public void add(int index, E element) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index > size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheckForAdd(index);

        // 当前动态数组的元素个数为size,我们确保需要size+1个容量
        ensureCapacity(size + 1);

        for (int i = size - 1; i >= index; i --) {
            elements[i + 1] = elements[i];
        }
        elements[index] = element;
        size ++;
    }

    // 确保有needCapacity的容量
    private void ensureCapacity(int needCapacity) {
        // 当前容量为nowCapacity
        int nowCapacity = elements.length;
        // 当前容量大于等于所需要的容量，容量够
        if (nowCapacity >= needCapacity) return;
        // 容量不够,则扩容至1.5倍
        int newCapacity = nowCapacity + (nowCapacity >> 1);
        E[] newElements = (E[])new Object[newCapacity];

        // 拷贝元素
        for(int i = 0; i < elements.length; i ++) {
            newElements[i] = elements[i];
        }
        elements = newElements;

        System.out.println(nowCapacity + "扩容为：" + newCapacity);
    }

    // 返回index索引位置对应的元素
    public E get(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);
        return elements[index];
    }

    // 删除index索引位置对应的元素,并返回所删除的元素
    public E remove(int index) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }
        rangeCheck(index);

        // 保存要被删除的值
        E remove = elements[index];

        // 从被删除的后一个元素开始往前移动
        for (int i = index + 1; i < size; i ++) {
            elements[i - 1] = elements[i];
        }

        // (内存管理细节)将最后一个元素变为null
        elements[size - 1] = null;

        size --;

        return remove;
    }

    // 设置index位置的元素,并返回旧值
    public E set(int index, E element) {
//        // 判断index索引位置是否合法,不合法抛出IndexOutOfBoundsException异常
//        if (index < 0 || index >= size) {
//            throw new IndexOutOfBoundsException("Index:" + index + ", Size = " + size);
//        }

        rangeCheck(index);

        // 保存当前索引的旧值
        E old = elements[index];
        // 设置index位置的新值
        elements[index] = element;

        return old;
    }

    // 查看指定元素第一次出现的位置,如果找不到则返回-1
    public int indexOf(E element) {
        // 遍历动态数组。注意size和elements.length的区别

        if (element == null) {
            for (int i = 0; i < size; i ++) {
                if (elements[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i ++) {
                if (element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    // 清除所有元素
    public void clear() {
        //size = 0;
        // (内存管理细节)对象内存清空，但是对象数组所分配的内存还在
        for (int i = 0; i < size; i ++) {
            elements[i] = null;
        }
        size = 0;
    }

    // 打印数组
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(elements[i]);
                break;
            }
            sb.append(elements[i]).append(", ");
        }
        sb.append("]");

        return sb.toString();
    }
}

三、(不带虚拟头节点)单链表的常用操作

3.1、清空操作clear()

@Override
public void clear() {
    size = 0;
    first = null;
}
  • 当first指向null的时候，后面的Node将会被Java自动回收
3.2、添加操作add(int index, E element)—不带虚拟头节点

编写一个node方法用于获得index位置的节点

// node方法用于获取index位置的节点
private Node<E> node(int index) {
    rangeCheck(index);
    Node<E> cur = first;
    for (int i = 0; i < index; i ++) {
        cur = cur.next;
    }
    return cur;
}

@Override
public void add(int index, E element) {
    // 判断index是否合法
    rangeCheckForAdd(index);
    if (index == 0) {
        Node<E> newNode = new Node<>(element, first);
        first = newNode;
    } else {
        Node<E> preNode = node(index - 1);
        Node<E> newNode = new Node<>(element, preNode.next);
        preNode.next = newNode;
    }
    size ++;
}

在编写链表相关操作代码过程中，要注意边界测试，比如index = 0，size - 1，size时。先写出一般情况，然后再考虑边界问题。

3.3、删除元素remove(int index)—不带虚拟头节点

@Override
public E remove(int index) {
    rangeCheck(index);
    E delEle;
    if (index == 0) {
        delEle = first.element;
        first = first.next;
    } else {
        Node<E> preNode = node(index - 1);
        delEle = preNode.next.element;
        preNode.next = preNode.next.next;
    }
    size --;
    return delEle;
}

四、(不带虚拟头节点)单链表的相关代码

package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-10-19:27
 */
public class LinkedList<E> extends AbstractList<E> {

    // 链表的头结点
    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;
        }
    }

    @Override
    public void clear() {
        size = 0;
        first = null;
    }

    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        return null;
    }

    @Override
    public void add(int index, E element) {
        // 判断index是否合法
        rangeCheckForAdd(index);
        if (index == 0) {
            Node<E> newNode = new Node<>(element, first);
            first = newNode;
        } else {
            Node<E> preNode = node(index - 1);
            Node<E> newNode = new Node<>(element, preNode.next);
            preNode.next = newNode;
        }
        size ++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        E delEle;
        if (index == 0) {
            delEle = first.element;
            first = first.next;
        } else {
            Node<E> preNode = node(index - 1);
            delEle = preNode.next.element;
            preNode.next = preNode.next.next;

        }
        size --;
        return delEle;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> cur = first;
            for (int i = 0; i < size; i ++) {
                if (cur.element == null) return i;
                cur = cur.next;
            }
        } else {
            Node<E> cur = first;
            for (int i = 0; i < size; i ++) {
                if (element.equals(cur.element)) return i;
                cur = cur.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    // node方法用于获取index位置的节点
    private Node<E> node(int index) {
        rangeCheck(index);
        Node<E> cur = first;
        for (int i = 0; i < index; i ++) {
            cur = cur.next;
        }
        return cur;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        Node<E> cur = first;
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(cur.element);
                break;
            }
            sb.append(cur.element).append(", ");
            cur = cur.next;
        }
        sb.append("]");

        return sb.toString();
    }
}

五、(带虚拟头结点)单链表的相关代码

为了统一头节点和非头节点的删除、添加处理逻辑，可以在最前面增加一个虚拟头节点(不存储数据)

LeeCode707. 设计链表

六、ArrayList和LinkedList的时间复杂度

  • size是数据规模n

注意：链表、添加删除那一刻的时间复杂度是O(1)，整体操作平均下来是O(n)

双向链表

Java官方的LinkedList底层实现就是双向链表

一、双向链表的设计

public class DoubleLinkedList<E> extends AbstractList<E> {
    private int size;
    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        private Node<E> prev;
        private E element;
        private Node<E> next;

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

二、双向链表的常用操作

2.1、添加操作add(int index, E element)(重点)

@Override
public void add(int index, E element) {
    if (index == size) {
        if (size == 0) {
            first = new Node<>(null, element, null);
            last = first;
        } else {
            Node<E> prev = node(size - 1);
            Node<E> newNode = new Node<>(prev, element, null);
            prev.next = newNode;
            last = newNode;
        }
        size ++;
    } else {
        Node<E> next = node(index);
        Node<E> prev = next.prev;
        Node<E> newNode = new Node<>(prev, element, next);
        next.prev = newNode;

        if (prev == null) {
            first = newNode;
        } else {
            prev.next = newNode;
        }
        size ++;
    }
}
2.2、删除操作remove(int index)(重点)

@Override
public E remove(int index) {
    rangeCheck(index);
	
    Node<E> node = node(index);
    Node<E> prev = node.prev;
    Node<E> next = node.next;
    
    if (prev == null) { // index ==0
        first = next;
    } else {
        prev.next = next;
    }
    
    if (next == null) { // index == size - 1
        last = prev;
    } else {
        next.prev = prev;
    }
   	size --;
    return node.element;
}

思路：先写一般情况，然后再考虑左右边界优化代码

2.3、获取操作get(int index)
@Override
public int indexOf(E element) {
    Node<E> cur = null;
    if (element == null) {
        cur = first;
        for (int i = 0; i < size; i ++) {
            if (cur.element == element) return i;
            cur = cur.next;
        }
    } else {
        cur = first;
        for (int i = 0; i < size; i ++) {
            if (element.equals(cur.element)) return i;
            cur = cur.next;
        }
    }
    return ELEMENT_NOT_FOUND;
}

思路：先写一般情况，然后再考虑左右边界优化代码

Node node = new Node(index)；// 当前节点

Node pre = node.prev；// 前一节点

Node next = node.next；// 后一节点

三、双向链表的相关代码

package DataStructure._02链表;

/**
 * @author keyongkang
 * @date 2022-07-12-23:04
 */
public class DoubleLinkedList<E> extends AbstractList<E> {
    private Node<E> first;
    private Node<E> last;

    private static class Node<E> {
        private Node<E> prev;
        private E element;
        private Node<E> next;

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


    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public E get(int index) {
        rangeCheck(index);
        Node<E> cur = null;
        if (index < (size >> 1)) {
            cur = first;
            for (int i = 0; i < index; i ++) {
                cur = cur.next;
            }
        } else {
            cur = last;
            for (int i = size - 1; i > index; i --) {
                cur = cur.prev;
            }
        }

        return cur.element;
    }

    @Override
    public E set(int index, E element) {
        rangeCheck(index);

        return node(index).element;
    }

    @Override
    public void add(int index, E element) {
        if (index == size) {
            if (size == 0) {
                first = new Node<>(null, element, null);
                last = first;
            } else {
                Node<E> prev = node(size - 1);
                Node<E> newNode = new Node<>(prev, element, null);
                prev.next = newNode;
                last = newNode;
            }
            size ++;
        } else {
            Node<E> next = node(index);
            Node<E> prev = next.prev;
            Node<E> newNode = new Node<>(prev, element, next);
            next.prev = newNode;

            if (prev == null) {
                first = newNode;
            } else {
                prev.next = newNode;
            }
            size ++;
        }
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

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

        return null;
    }

    @Override
    public int indexOf(E element) {
        Node<E> cur = null;
        if (element == null) {
            cur = first;
            for (int i = 0; i < size; i ++) {
                if (cur.element == element) return i;
                cur = cur.next;
            }
        } else {
            cur = first;
            for (int i = 0; i < size; i ++) {
                if (element.equals(cur.element)) return i;
                cur = cur.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }


    /**
     * 获取index位置对应的节点对象
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        rangeCheck(index);

        if (index < (size >> 1)) {
            Node<E> node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else {
            Node<E> node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size = ").append(size).append(", ").append("[");
        Node<E> cur = first;
        for (int i = 0; i < size; i ++) {
            if (i == size - 1) {
                sb.append(cur.element);
                break;
            }
            sb.append(cur.element).append(", ");
            cur = cur.next;
        }
        sb.append("]");

        return sb.toString();
    }
}

四、双向链表vs单向链表

五、双向链表vs动态数组

单向循环链表