Java 线性表实现：带头尾指针的链表 LinkedList

一、基础结构定义

与动态数组类似，本实现基于接口 CList<E>。

1. 结点定义 (CNode)

包含数据域 data 和指针域 next。

public class CNode<E> {
    E data;
    CNode<E> next;

    public CNode() {
        this.data = null;
        this.next = null;
    }

    public CNode(E data) {
        this.data = data;
        this.next = null;
    }

    public CNode(E data, CNode<E> next) {
        this.data = data;
        this.next = next;
    }
}

2. 链表属性与构造 (CLinkedList)

属性：

• 头指针 head（存储数据）
• 尾指针 rear
• 元素个数 size

包含 head 和 rear 使得对数据进行头部和尾部的添加和删除操作时，需要特殊处理并更新指针。此处 head 必须实例化，确保后续操作有一个有效的对象基础。

private CNode<E> head = new CNode<>();
private CNode<E> rear;
private int size;

构造方法： 在属性定义中，head 已经初始化。在 CNode<E> 的构造函数中，已将 head.next 和 head.data 初始化为 null，因此直接让 rear = head 即可。

public CLinkedList() {
    this.rear = head;
    this.size = 0;
}

public CLinkedList(E e) {
    CNode<E> newNode = new CNode<>(e);
    this.head = newNode;
    this.rear = head;
    this.size = 1;
}

二、核心功能实现

1. 常用方法

size() / isEmpty()

获取链表长度及判断是否为空。

toArray()

同动态数组，使用匿名内部类，从外部传入数组 nv，将数据复制到 nv 中，再将 nv 返回。

public E[] toArray(E[] nv, Clone<E> clone) {
    CNode<E> current = head;
    for (int i = 0; i < size; i++) {
        nv[i] = clone.clone(current.data);
        current = current.next;
    }
    return nv;
}

public E[] toArray(int si, int ei, E[] nv, Clone<E> clone) {
    if (si <= 0 || ei < si || ei > size) {
        throw new IndexOutOfBoundsException("索引越界 size=" + size);
    }
    CNode<E> current = getNode(si);
    for (int i = 0; i < ei - si + 1; i++) {
        nv[i] = clone.clone(current.data);
        current = current.next;
    }
    return nv;
}

toString()

用 StringBuilder 实现，append() 添加，toString() 返回字符串对象。

public String toString() {
    System.out.println("当前链表长度 size = " + size);
    if (isEmpty()) {
        StringBuilder sb = new StringBuilder("[ ]");
        return sb.toString();
    } else {
        CNode<E> current = head;
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size - 1; i++) {
            sb.append(current.data).append(",");
            current = current.next;
        }
        sb.append(current.data).append("]");
        return sb.toString();
    }
}

2. 增操作（注意头尾的特殊处理）

add() / addFirst()

• add()：尾插法
• addFirst()：头插法

无论是头插法还是尾插法，添加第一个元素都需要特殊处理，判断是否为空链表（用 isEmpty()，size == 0，head.data == null）。

// 尾插法
public void add(E e) {
    CNode<E> newNode = new CNode<>(e);
    // 如果添加的第一个元素，特殊处理
    if (head.data == null) {
        head = newNode;
        rear = head;
        size = 1;
    } else {
        rear.next = newNode;
        rear = newNode;
        size++;
    }
}

// 头插法
public void addFirst(E e) {
    CNode<E> newNode = new CNode<>(e);
    // 如果添加的第一个元素，特殊处理
    if (head.data == null) {
        head = newNode;
        rear = head;
        size = 1;
    } else {
        newNode.next = head;
        head = newNode;
        size++;
    }
}

addAll()

• 添加数组 E[]：对于每一个数组中的元素，判断是否为空，并调用 add()。
• 添加线性表 CList：
  1. 如果 clist 是链表，直接将 rear 节点连接到添加链表的 head 节点上，getNode(1) 得到 head 节点，同 add 方法一样，需要判断原链表是否为空，是否第一次添加元素。
  2. 如果是动态数组，调 get() 方法得到每个元素，再用 add() 添加。 链表也可以用方法 2，但是方法 1 更高效，不用反复调用 getNode()。

public void addAll(E[] objects) {
    for (E object : objects) {
        if (object != null) {
            add(object);
        }
    }
}

public void addAll(CList<E> clist) {
    // 如果 clist 是一个链表，不用重复调用 get 方法，直接让两个链表连接起来就行
    if (clist instanceof CLinkedList<E> linkedList) {
        // 需要判断原链表是否为空，需要特殊处理
        if (head.data == null) {
            head = linkedList.getNode(1);
            rear = linkedList.getNode(clist.size());
            size = size + clist.size();
        } else {
            rear.next = linkedList.getNode(1);
            rear = linkedList.getNode(clist.size());
            size = size + clist.size();
        }
    } else {
        for (int i = 0; i < size; i++) {
            add(clist.get(i + 1));
        }
    }
}

insert() / insertAll()

指定位置插入元素。指定位置插入时，需要考虑插入在链表头部和尾部的特殊情况（涉及 head 和 rear 的更新），所以分为这两个方法都要分为三种情况：插到头部（index = 1）；中间（1 < index < size）；尾部（index = size）。

public void insert(int index, E e) {
    CNode<E> newNode = new CNode<>(e);
    // 插入位置是第一个位置，特殊处理
    if (index == 1) {
        newNode.next = head.next;
        head = newNode;
        size++;
        // 插入位置是最后一个位置，特殊处理
    } else if (index == size) {
        rear.next = newNode;
        rear = newNode;
        size++;
        // 中间位置
    } else {
        // 获得插入位置的前一个元素
        CNode<E> current = getNode(index - 1);
        newNode.next = current.next;
        current.next = newNode;
        size++;
    }
}

public void insertAll(int index, E[] es) {
    // 将数组 es 转化为一个链表
    CLinkedList<E> newLinkedList = new CLinkedList<>();
    for (int i = 0; i < es.length; i++) {
        newLinkedList.add(es[i]);
    }
    // 获得新链表的头尾节点
    CNode<E> newNodeHead = newLinkedList.getNode(1);
    CNode<E> newNodeRear = newLinkedList.getNode(newLinkedList.size());

    if (index == 1) {
        newNodeRear.next = head;
        head = newNodeHead;
    } else if (index == size) {
        rear.next = newNodeHead;
        rear = newNodeRear;
    } else {
        CNode<E> current = getNode(index - 1);
        newNodeRear.next = current.next;
        current.next = newNodeHead;
    }
    size = size + es.length;
}

3. 删操作（注意头尾的特殊处理）

remove()

分四种情况，除了在处理头和尾的特殊情况，同时还要判断删除的元素是否为最后一个元素。如果是最后一个元素，则将 head 和 rear 的 data 和 next 都设置为空指针 null，size 设置为 0，toEmpty() 完成该操作，将链表设置为空链表。

public E remove(int index) {
    if (index <= 0 || index > size) {
        throw new IndexOutOfBoundsException("索引越界 size=" + size);
    }
    CNode<E> removeNode = getNode(index);
    if (size == 1) {
        head.data = null;
        head.next = null;
        rear = head;
        size = 0;
    } else if (index == 1) {
        head = head.next;
        size--;
    } else if (index == size) {
        CNode<E> current = getNode(index - 1);
        rear = current;
        size--;
    } else {
        CNode<E> current = getNode(index - 1);
        current.next = removeNode.next;
        size--;
    }
    return removeNode.data;
}

public void toEmpty() {
    head.data = null;
    head.next = null;
    rear = head;
    size = 0;
}

removeAll()

• 指定范围删除：分为四种情况，涉及头尾都需要特殊处理，还有删除完链表最后一个元素，链表设置为空链表 toEmpty()。

public E[] removeAll(int si, int ei) {
    if (si <= 0 || ei < si || ei > size) {
        throw new IndexOutOfBoundsException("索引越界 size=" + size);
    }
    if (si == 1 && ei != size) {
        head = getNode(ei).next;
    } else if (si != 1 && ei == size) {
        rear = getNode(si - 1);
    } else if (si == 1 && ei == size) {
        toEmpty();
    } else {
        CNode<E> siNode = getNode(si - 1);
        CNode<E> eiNode = getNode(ei + 1);
        siNode.next = eiNode;
    }
    size = size - (ei - si + 1);
    return null;
}

• 指定数组删除： 思想：current 从 head 节点开始遍历整个链表，对于每一个元素，判断是否删除（用一个 for 循环判断是否存在于数组 objects 中），用 count 来记录需要删除元素的序号，将 count 传入 remove() 中进行删除。这里通过 count 记录删除元素的序号，来通过 remove() 实现删除，免去了头尾的边界特殊处理，这样的好处是不需要再写头尾的特殊处理，缺点是增加了 getNode() 函数的调用次数，时间复杂度高。 对于 for 循环的处理结果，用 flag 标志将结果带出来。如果 flag = 1 代表，该元素需要删除，此处注意不需要 count++，因为删除当前元素，current 向后移动指向的元素序号依然是 count，flag = 0 时，count++。同时注意，无论当前元素是否需要删除，current 都要向后移。

public boolean removeAll(E[] objects) {
    if (objects == null || objects.length == 0) {
        throw new IndexOutOfBoundsException("传入数组为空");
    }
    CNode<E> current = head;
    int count = 1;
    while (current != null) {
        int flag = 0;
        // 记录当前节点是否需要删除
        for (int j = 0; j < objects.length; j++) {
            if (current.data.equals(objects[j])) {
                flag = 1;
                break;
            }
        }
        current = current.next;
        // 需要删除元素
        if (flag == 1) {
            remove(count);
        } else {
            count++;
        }
    }
    return true;
}

removeForE()

用前后指针 prev 和 current 实现删除。当判断到当前元素需要删除时，分为三种情况：头部，中间，尾部，如果不删除则 prev 和 current 向后移动。

public int removeForE(Object e) {
    CNode<E> current = head;
    CNode<E> prev = null;
    while (current != null) {
        if (current.data.equals(e)) {
            // 第一个节点
            if (prev == null) {
                head = head.next;
                current = current.next;
                size--;
                // 如果删除的元素是最后一个节点
            } else if (current.next == null) {
                rear = prev;
                rear.next = null;
                size--;
                break;
                // 删除的是中间元素
            } else {
                prev.next = current.next;
                current = current.next;
                size--;
            }
        } else {
            prev = current;
            current = current.next;
        }
    }
    return 1;
}

4. 查操作

get() / getNode() / getForE()

public E get(int index) {
    CNode<E> current = getNode(index);
    return current.data;
}

public CNode<E> getNode(int index) {
    if (index <= 0 || index > size) {
        throw new IndexOutOfBoundsException("索引越界 size=" + size);
    }
    // 如果 index = 1，则返回 head 节点
    int count = 1;
    CNode<E> current = head;
    while (count < index && current != null) {
        current = current.next;
        count++;
    }
    return current;
}

public boolean getForE(E e) {
    CNode<E> current = head;
    for (int i = 0; i < size; i++) {
        if (current.data.equals(e)) {
            return true;
        } else {
            current = current.next;
        }
    }
    return false;
}

indexForFirst() / indexForLast()

• indexForFirst()：逻辑简单，就是用 count 计数。
• indexForLast()：不能从后往前遍历，这里将链表逆置（头插法 addFirst()），创建一个新的链表，再用 indexForFirst 处理逆置后的链表，返回的 count 就是从后往前计数的结果。

public int indexForFirst(Object e) {
    CNode<E> current = head;
    int count = 1;
    while (current != null) {
        if (current.data.equals(e)) {
            return count;
        } else {
            current = current.next;
            count++;
        }
    }
    return count <= size ? count : -1;
}

public int indexForLast(Object e) {
    CLinkedList<E> RLinkedList = new CLinkedList<>();
    for (int i = 1; i <= size; i++) {
        RLinkedList.addFirst(get(i));
    }
    int count = RLinkedList.indexForFirst(e);
    return count;
}

5. 改操作

replace()

public E replace(int index, E e) {
    CNode<E> newNode = new CNode<>(e);
    CNode<E> current = getNode(index);
    if (index == 1) {
        newNode.next = head.next;
        head = newNode;
    } else if (index == size) {
        CNode<E> prev = getNode(index - 1);
        prev.next = newNode;
        rear = newNode;
    } else {
        CNode<E> prev = getNode(index - 1);
        newNode.next = current;
        prev.next = newNode;
    }
    return current.data;
}

replaceAll(E oe, E ne)

处理方法类似于 removeForE()。创建一个 current 和 prev，方便对元素修改，替换元素和删除一个元素相似。

public int replaceAll(E oe, E ne) {
    CNode<E> current = head;
    CNode<E> prev = null;
    int count = 0;
    while (current != null) {
        if (current.data.equals(oe)) {
            count++;
            CNode<E> newNode = new CNode<>(ne);
            if (prev == null) {
                newNode.next = head.next;
                head = newNode;
                prev = head;
                current = current.next;
            } else if (current.next == null) {
                prev.next = newNode;
                rear = newNode;
                break;
            } else {
                prev.next = newNode;
                newNode.next = current.next;
                prev = newNode;
                current = current.next;
            }
        } else {
            prev = current;
            current = current.next;
        }
    }
    return count;
}

replaceAll(int si, E[] objects)

对于数组创建一个链表，再将其插入不同位置。

public E[] replaceAll(int si, E[] objects) {
    if (si <= 0 || si > size) {
        throw new IndexOutOfBoundsException("索引越界 size=" + size);
    }
    CLinkedList<E> newLinkedList = new CLinkedList<>();
    for (int i = 0; i < objects.length; i++) {
        newLinkedList.add(objects[i]);
    }
    if (si == 1) {
        newLinkedList.rear.next = head;
        head = newLinkedList.head;
    } else if (si == size) {
        rear.next = newLinkedList.head;
        rear = newLinkedList.rear;
    } else {
        CNode<E> prev = getNode(si - 1);
        CNode<E> current = getNode(si);
        prev.next = newLinkedList.head;
        newLinkedList.rear.next = current;
    }
    size = size + objects.length;
    return null;
}