双向链表

发表于 | 分类于
字数统计: 627 | 阅读时长 ≈ 3

1.单向链表与双向链表的区别

1、单向链表查找方向只能是一个方向，而双向链表可以向前或向后查找。
2、单向链表不能自我删除，需要靠赋辅助节点，而双向链表则可以自我删除。

2.双向链表的创建、插入、删除和显示

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
package linkedlist;

public class DoubleLinkedListDemo {
	public static void main(String[] args) {
		// 创建节点
		HeroNode2 hero1 = new HeroNode2(1000, "wd");
		HeroNode2 hero2 = new HeroNode2(1001, "lz");
		HeroNode2 hero3 = new HeroNode2(1002, "lp");
		// 创建链表
		DoubleLinkedList heroList2 = new DoubleLinkedList();
		// 添加节点到 链表
		heroList2.add(hero1);
		heroList2.add(hero2);
		heroList2.add(hero3);
		// 遍历链表
		heroList2.list(heroList2.head);
		// 修改节点
		heroList2.update(new HeroNode2(1002, "gf"));
		// 再次遍历
		System.out.println("修改后： ");
		heroList2.list(heroList2.head);
		// 删除id=1001的节点
		heroList2.delete(1000);
		// 再次遍历
		System.out.println("删除id=1000的节点后： ");
		heroList2.list(heroList2.head);
	}
}

//定义HeroNode2 ,每一个HeroNode 对象就是一个节点
class HeroNode2 {
	public int id;
	public String name;
	public HeroNode2 pre; // 指向前一个节点
	public HeroNode2 next;// 指向下一个节点

	public HeroNode2() {
		super();
	}

	public HeroNode2(int id, String name) {
		this.id = id;
		this.name = name;
	}

	@Override
	public String toString() {
		return "HeroNode2 [id=" + id + ", name=" + name + "]";
	}
}

// 创建一个双向链表的类
class DoubleLinkedList {
	HeroNode2 head = new HeroNode2();

	// 从链表尾添加节点
	public void add(HeroNode2 newNode) {
		HeroNode2 cur = head;
		// 找到最后一个节点
		while (true) {
			if (cur.next == null) {
				break;
			}
			cur = cur.next;
		} // 循环结束后cur指向最后一个节点
			// 将新节点添加到链表中
		cur.next = newNode;
		newNode.pre = cur;
	}

	// 遍历双向链表
	public void list(HeroNode2 head) {
		if (head.next == null) {
			System.out.println("链表为空！");
			return;
		}
		HeroNode2 cur = head.next;
		while (true) {
			if (cur == null) {
				return;
			}
			System.out.println(cur);
			cur = cur.next;
		}
	}

	// 根据id修改节点
	public void update(HeroNode2 newNode) {
		if (head.next == null) {
			System.out.println("链表为空！");
		}
		HeroNode2 cur = head.next;
		while (true) {
			if (cur == null) {
				// 遍历完成没有找到
				System.out.println("没有id相同的节点~");
				return;
			}
			if (cur.id == newNode.id) {
				// 找到该节点
				cur.name = newNode.name;
				return;
			}
			cur = cur.next;
		}
	}

	// 删除指定id的节点
	public void delete(int id) {
		if (head.next == null) {
			System.out.println("链表位空！");
			return;
		}
		HeroNode2 cur = head.next;
		while (true) {
			if (cur == null) {
				System.out.println("没有找到指定id的节点~");
				return;
			}
			if (cur.id == id) {
				// 找到该节点 将待删除节点前后的节点链接到一起
				if (cur.next == null) {// 待删除的节点是最后一个节点
					cur.pre.next = null;
					return;
				} else {
					cur.pre.next = cur.next;
					cur.next.pre = cur.pre;
					return;
				}
			}
			cur = cur.next;
		}
	}
}