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 关键字时,需要根据具体的应用场景进行选择和优化。