LinkedList

LinkedList 是 Java 中实现双向链表的一个类，它实现了 List 接口和 Deque 接口。LinkedList 可以用作栈、队列和双端队列。在本文中，我们将详细介绍 LinkedList 的实现原理，并结合源码和示例代码进行解释。

LinkedList 的结点

LinkedList 的结点是一个静态内部类 Node，它包含三个属性：item 表示结点存储的元素，next 表示下一个结点，prev 表示上一个结点。Node 类的代码如下：

 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;
    }
}

LinkedList 的属性

LinkedList 的主要属性包括 size 表示链表的长度，first 表示链表的第一个结点，last 表示链表的最后一个结点。LinkedList 类的部分代码如下：

1
2
3
4
5
6
7
8
9


public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    ...
}

LinkedList 的添加操作

LinkedList 提供了多种添加操作，如 add()、addFirst()、addLast() 等。这些操作的实现原理基本相同，都是通过创建新的结点，并将其插入到链表中实现的。以 add() 操作为例，其代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public boolean add(E e) {
    linkLast(e);
    return true;
}

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++;
}

可以看出，add() 操作通过 linkLast() 方法将新的结点插入到链表的末尾。linkLast() 方法首先创建一个新的结点 newNode，然后将其插入到链表的末尾，并更新 last 和 size 属性。

LinkedList 的删除操作

LinkedList 提供了多种删除操作，如 remove()、removeFirst()、removeLast() 等。这些操作的实现原理基本相同，都是通过将结点从链表中移除实现的。以 remove() 操作为例，其代码如下：

 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
44


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) {
    // assert x != null;
    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;
}

可以看出，remove() 操作通过遍历链表，查找要删除的结点，然后通过 unlink() 方法将其从链表中移除。unlink() 方法首先将结点的前驱和后继结点连接起来，然后更新 first、last 和 size 属性。

LinkedList 的访问操作

LinkedList 提供了多种访问操作，如 get()、getFirst()、getLast() 等。这些操作的实现原理基本相同，都是通过遍历链表，查找指定位置的结点实现的。以 get() 操作为例，其代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(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;
    }
}

可以看出，get() 操作通过 node() 方法查找指定位置的结点，然后返回结点存储的元素。node() 方法根据索引的大小，从链表的首部或尾部开始遍历链表，查找指定位置的结点。

示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        System.out.println(linkedList);  // [1, 2, 3]

        linkedList.addFirst(0);
        linkedList.addLast(4);
        System.out.println(linkedList);  // [0, 1, 2, 3, 4]

        linkedList.remove(0);
        linkedList.removeLast();
        System.out.println(linkedList);  // [1, 2, 3]

        System.out.println(linkedList.get(1));  // 2
        System.out.println(linkedList.getFirst());  // 1
        System.out.println(linkedList.getLast());  // 3
    }
}

总之，LinkedList 是 Java 中实现双向链表的一个类，它提供了多种添加、删除和访问操作。LinkedList 的实现原理是通过结点的前驱和后继指针，将结点连接成一个链表。LinkedList 的操作实现相对简单，但是在大规模数据操作时，性能可能会比 ArrayList 等数组实现的列表低。因此，在使用 LinkedList 时，需要根据具体的应用场景进行选择和优化。

静态内部类

静态内部类（Static Nested Class）是 Java 中的一种内部类，它具有 static 修饰符，与外部类没有直接的关联。静态内部类有以下特点：

静态内部类可以直接访问外部类的静态成员，包括静态变量和静态方法，但不能直接访问外部类的非静态成员。
静态内部类不依赖于外部类的实例，可以在外部类被加载时就被加载，并且可以使用静态内部类的实例，而无需创建外部类的实例。
静态内部类可以拥有自己的静态成员和静态方法，并且可以被声明为 final 类或接口。

静态内部类的作用和使用场景如下：

封装和组织代码

静态内部类可以用来封装和组织代码，将相关的类和接口组织在一起，提高代码的可读性和可维护性。例如，在一个大型的类中，可以将辅助类或接口声明为静态内部类，以便更好地组织代码。

实现单例模式

静态内部类可以用来实现单例模式，通过在静态内部类中创建外部类的实例，并提供一个公共的静态方法获取该实例，可以保证外部类只有一个实例。这种实现方式可以避免线程安全问题，并且可以实现延迟加载。

实现回调接口

静态内部类可以用来实现回调接口，将回调接口声明为静态内部类，并在外部类中创建静态内部类的实例，以便在回调方法中访问外部类的静态成员。这种实现方式可以避免内部类持有外部类的引用，从而减少内存消耗。

实现工具类

静态内部类可以用来实现工具类，将工具类声明为静态内部类，并在外部类中提供一个公共的静态方法获取该实例，可以避免工具类被实例化，并且可以实现工具类的单例化。

示例代码：

 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


public class OuterClass {
    private static int staticField = 1;
    private int instanceField = 2;

    public static class StaticNestedClass {
        private static int staticNestedField = 3;
        private int nestedField = 4;

        public static void staticNestedMethod() {
            System.out.println("staticNestedField = " + staticNestedField);
            System.out.println("staticField = " + staticField);
        }

        public void nestedMethod() {
            System.out.println("nestedField = " + nestedField);
            System.out.println("instanceField = " + new OuterClass().instanceField);
        }
    }

    public static void main(String[] args) {
        OuterClass.StaticNestedClass.staticNestedMethod();  // 输出：staticNestedField = 3, staticField = 1

        OuterClass.StaticNestedClass nestedClass = new OuterClass.StaticNestedClass();
        nestedClass.nestedMethod();  // 输出：nestedField = 4, instanceField = 2
    }
}

总之，静态内部类是 Java 中一种非常有用的内部类，它可以用来封装和组织代码，实现单例模式、回调接口和工具类等。在使用静态内部类时，需要根据具体的应用场景进行选择和优化。

transient 关键字

transient 是 Java 中的一个关键字，它用来修饰成员变量，表示该变量不是对象的持久化数据的一部分，在对象被序列化和反序列化时，该变量将被忽略。

transient 关键字的作用和使用场景如下：

提高序列化和反序列化的效率

在对象被序列化时，会将对象的所有成员变量都序列化到磁盘或网络上，如果对象中有一些成员变量不需要被序列化，可以使用 transient 关键字修饰这些成员变量，以提高序列化和反序列化的效率。

保护敏感数据

在对象被序列化时，如果对象中包含一些敏感数据，例如密码、密钥等，可以使用 transient 关键字修饰这些成员变量，以避免这些敏感数据被序列化和传输。

避免对象状态的不一致

在对象被序列化和反序列化时，如果对象中包含一些与外部资源相关的成员变量，例如文件描述符、网络连接等，可能会导致对象状态的不一致，可以使用 transient 关键字修饰这些成员变量，以避免这些成员变量被序列化和传输。

示例代码：

 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


import java.io.FileOutputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;

public class TransientTest implements Serializable {
    private static final long serialVersionUID = 1L;

    private int id;
    private transient String password;

    public TransientTest(int id, String password) {
        this.id = id;
        this.password = password;
    }

    public static void main(String[] args) throws Exception {
        TransientTest test = new TransientTest(1, "123456");

        FileOutputStream fos = new FileOutputStream("test.obj");
        ObjectOutputStream oos = new ObjectOutputStream(fos);
        oos.writeObject(test);
        oos.close();

        System.out.println("id = " + test.id);
        System.out.println("password = " + test.password);
    }
}

在上面的示例代码中，TransientTest 类实现了 Serializable 接口，表示该类可以被序列化。TransientTest 类中包含两个成员变量 id 和 password，其中 password 变量使用 transient 关键字修饰，表示该变量不是对象的持久化数据的一部分，在对象被序列化时，该变量将被忽略。在 main 方法中，创建了一个 TransientTest 对象，并将其序列化到磁盘上，然后输出了 id 和 password 的值，可以看到 password 的值已经被忽略了。

总之，transient 关键字是 Java 中一种非常有用的关键字，它可以用来提高序列化和反序列化的效率，保护敏感数据，避免对象状态的不一致等。在使用 transient 关键字时，需要根据具体的应用场景进行选择和优化。

文章目录

LinkedList

LinkedList

静态内部类

transient 关键字

See Also

最近文章

福利派送

分类

标签

友情链接

其它