LinkedList

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

  1. 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;
    }
}
  1. 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;
    ...
}
  1. 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 属性。

  1. 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 属性。

  1. 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. 示例代码
 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 修饰符,与外部类没有直接的关联。静态内部类有以下特点:

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

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

  1. 封装和组织代码

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

  1. 实现单例模式

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

  1. 实现回调接口

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

  1. 实现工具类

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

示例代码:

 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 关键字的作用和使用场景如下:

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

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

  1. 保护敏感数据

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

  1. 避免对象状态的不一致

在对象被序列化和反序列化时,如果对象中包含一些与外部资源相关的成员变量,例如文件描述符、网络连接等,可能会导致对象状态的不一致,可以使用 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 关键字时,需要根据具体的应用场景进行选择和优化。