链表 Linked List（双向链表）_list 与双向链表 区别

单链表与双链表的区别

单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以单链表删除节点时，总是找到temp的下一个节点来删除的

双链表DoubleLinkedList

大部分代码与单链表的实例相同：单链表实例：单击前往
同理先创建一个Node节点类。区别在于需要添加一个指向前一个节点的变量pre；

class Node2 {
	public int no;
	public String name;
	public String head;
	public Node2 next;// 指向下一个数据结点
	public Node2 pre;// 指向前一个数据结点
	public Node2(int Hno, String Hname, String Hhead) {
		this.no = Hno;
		this.name = Hname;
		this.head = Hhead;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "Node2 [no=" + no + ",name=" + name + ",head=" + head + "]";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在DoubleLinkedList双向链表类当中初始化一个头节点，和一个返回头结点的方法

// 初始化一个头节点,头节点不存放数据
	private Node2 headnode = new Node2(0, "", "");
	public Node2 getHead() {
		return headnode;
	}
1
2
3
4
5

遍历双向链表 ：与单链表一致从头到尾遍历

// 遍历双向链表
	public void list() {
		// 判断链表是否为空
		if (headnode.next == null) { // 头节点的next指向null
			System.out.println("链表为空");
			return;
		}
		Node2 temp = headnode.next; // 辅助变量，
		while (true) {
			if (temp == null) {
				// 遍历到最后,
				break;
			}
			// 不为空，输出节点信息
			System.out.println(temp);
			// 后移
			temp = temp.next;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

添加节点到双向链表 ：在单链表的基础上将添加节点的pre指向原来最后一个节点。

public void add(Node2 n) {
		// 不考虑编号顺序，直接在最后一个添加，最后结点next指向传过来的节点
		Node2 temp = headnode; // 辅助变量，指向头节点
		while (true) {
			if (temp.next == null) {
				break;
			}
			temp = temp.next;
		}
		// 添加节点，双向链表
		temp.next = n;
		n.pre = temp;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

添加节点到双向链表：按编号顺序添加 在这里按照单链表的思路：只需要将往前指的指针进行指向即可：如下图红线所示：

// 添加方法,排序
	public void addOrderBy(Node2 n) {
		// temp是所要添加节点的前一个位置的节点
		Node2 temp = headnode;
		boolean b = false;// 判断编号是否已经存在
		while (true) {
			if (temp.next == null) { // 节点的next值为null,表示找到最后一个节点
				break;
			}
			if (temp.next.no > n.no) {
				// 当节点的编号值大于这个添加的节点的编号,找到的前一个位置就是需要插入的位置
				break;
			} else if (temp.next.no == n.no) {
				// 编号相等表示编号已经存在
				b = true;
				break;
			}
			// 后移辅助节点用于循环遍历
			temp = temp.next;
		}
		if (b) {
			System.out.println("该编号已存在，编号为：" + n.no);
		} else {
			// 插入到temp后面
			n.next = temp.next;
			temp.next = n;
			n.next.pre = n.pre;
			n.pre = temp.pre;
		}
	}
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

根据节点的编号修改节点信息 双向链表 与单链表一致：

public void update(Node2 n) {
		// 判断是否为空
		if (headnode.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 找到要修改的节点
		Node2 temp = headnode.next;
		boolean b = false;// 判断找到这个编号节点
		while (true) {
			if (temp.next == null) { // 遍历到最后一个节点
				break;
			}
			if (temp.no == n.no) {
				// 找到了这个节点
				b = true;
				break;
			}
			// temp后移继续遍历
			temp = temp.next;
		}
		if (b) {
			// 修改值
			temp.name = n.name;
			temp.head = n.head;
		} else {
			System.out.println("没有这个编号:" + n.no);
		}
	}
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

节点删除 双向链表 实现自我删除

public void delete(int n) {
		if (headnode == null) {
			System.out.println("链表为空，");
			return;
		}
		Node2 temp = headnode.next;
		boolean b = false;// 是否找到这个n
		while (true) {
			if (temp == null) {// 遍历完成后跳出循环
				break;
			}
			if (temp.no == n) {// 找到了这个要删除的节点
				b = true;
				break;
			}
			temp = temp.next; // 往下继续遍历
		}
		if (b) {
			temp.pre.next = temp.next;
			// 需要判断删除的是不是最后一个节点。
			if (temp.next != null) {
				temp.next.pre = temp.pre;
			}
		} else {
			System.out.println("节点不存在：" + n);
		}
	}
}
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

定义一个测试类进行测试：

Node2 node1 = new Node2(1, "瓜皮1", "guapi1");
Node2 node2 = new Node2(2, "瓜皮2", "guapi2");
Node2 node3 = new Node2(3, "瓜皮3", "guapi3");
Node2 node4 = new Node2(4, "瓜皮4", "guapi4");

DoubleLinkedList DoubleLinkedList = new DoubleLinkedList();

DoubleLinkedList.add(node1);
DoubleLinkedList.add(node2);
DoubleLinkedList.add(node3);
DoubleLinkedList.add(node4);
DoubleLinkedList.list();

System.out.println("修改节点：");
Node2 node2hao = new Node2(2, "瓜皮2号", "guapi2hao");
DoubleLinkedList.update(node2hao);
DoubleLinkedList.list();

System.out.println("删除节点后：");
DoubleLinkedList.delete(1);
DoubleLinkedList.list();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

结果如下：