Java LinkedList

Java

链表

代码基于Java8

基本结构

从类声明上看，同时实现了List和Deque，暴露了内部是双链结构

LinkedList.java
1
2
3
4
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    //...
}

存储结构上,维护3个变量：链表长度，头结点和尾结点

LinkedList.java
1
2
3
transient int size = 0;
transient Node<E> first;
transient Node<E> last;

结点数据结构是一个静态内类，实现上很直观，前后指针加结点数据

LinkedList.java
1
2
3
4
5
6
7
8
9
10
11
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

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

序列化机制

类声明实现了序列化接口，并且变量全部标记为transient,说明序列化有定制处理
可以看出序列化并没有输出链表结点结构，只是链表长度和遍历输出的所有数据

LinkedList.java
1
2
3
4
5
6
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    s.writeInt(size);
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

反序列化根据数据重建链表，每个数据新生成一个结点，接在链表尾部

  • 标记原尾指针
  • 尾指针指向新结点
  • 如果原来没结点，那就是头结点，否则原尾指针结点接入新结点
LinkedList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    int size = s.readInt();
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

操作

取索引位置数据是列表的基本操作
实现基于遍历，随机访问性能比较差
因为是双链，遍历可以从头部或者尾部开始，取决于索引位置离哪边近，优化性能

LinkedList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

搜索无法判定离哪端近，因此都从头部开始搜，找到第一个就返回
与之对应还有从尾部遍历的lastIndexOF方法

LinkedList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

删除节点,先遍历到目标，然后断开操作

  • 标记目标的前后指针
  • 断开前指针
  • 断开后指针
LinkedList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

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

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

    x.item = null;
    size--;
    modCount++;
    return element;
}

尾部附加

LinkedList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void addLast(E e) {
    linkLast(e);
}
void linkLast(E e) {
    //获取现在尾部
    final Node<E> l = last;
    //创建新的尾节点，尾节点的next是null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        //原来是空链，那么尾节点也是头部
        first = newNode;
    else
        //原来非空，直接接上
        l.next = newNode;
    size++;
    modCount++;
}

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2018/05/23/java-linkedlist/