数据结构-双端链表和双向链表

1、双端链表
链表中保存着对最后一个节点的引用，这就是双端链表

package chap05;

import chap04.Node;

//双端链表
public class FirstLastLinkList {
	private Node first;//头结点
	private Node last;//尾结点
	
	  FirstLastLinkList() {
		first=null;
		last=null;
	}
	//插入一个节点，在头结点后进行插入
	public void insertFirst(long value) {
		Node node=new Node(value);
		if(isEmpty()) {
			last=node;
		}
		node.next=first;
		first=node;
	}
	//插入一个节点，在尾结点后进行插入
	public void insertLast(long value) {
		Node node=new Node(value);
		if(isEmpty()) {
			first=node;
		}else {
			last.next=node;
		}
		last=node;
	}
	
	//删除一个节点，在头结点后进行删除
	public Node deleteFirst() {
		Node temp=first;
		if(first.next==null) {
			last=null;
		}
		first=temp.next;
		return temp;
	}
	//显示方法
	public void display() {
		Node current=first;
		while(current!=null) {
			current.display();
			current=current.next;
		}
		System.out.println();
	}
	//查找
	public Node find(long value) {
		Node current=first;
		while(current.data!=value) {
			if(current.next==null) {
				return null;
			}
			current=current.next;
		}
		return current;
	}
	//删除方法，根据数据域来进行删除
	public Node delete(long value) {
		Node current=first;
		Node previous=first;
		while(current.data!=value) {
			if(current.next==null) {
				return null;
			}
			previous=current;
			current=current.next;
		}
		if(current==first) {
			first=first.next;
		}else {
			previous.next=current.next;
		}
		return current;
	}
	//判断是否为空
	public boolean isEmpty() {
		return first==null;
	}
}
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

测试类

package chap05;

public class TestFirstLastLinkList {
	public static void main(String[] args) {
		FirstLastLinkList f=new FirstLastLinkList();
		f.insertFirst(34);
		f.insertFirst(56);
		f.insertFirst(67);
		f.display();
		
		f.deleteFirst();
		f.display();
		
		f.insertLast(20);
		f.display();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果

2、双向链表
每个节点除了保存下一个节点的引用之外，同时还保存着对前一个节点的引用

package chap05;
//链节点，相当于车厢
public class Node {
	public long data;//数据域
	public Node next;//下一个节点域(指针域)
	public Node previous;//前一个节点域(指针域)
	
	public Node(long value) {
		this.data=value;
	}
	//显示方法
	public void display() {
		System.out.print(data+" ");
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

package chap05;

//双向链表
public class DoubleLinkList {
	private Node first;//头结点
	private Node last;//尾结点
	
	  DoubleLinkList() {
		first=null;
		last=null;
	}
	//插入一个节点，在头结点后进行插入
	public void insertFirst(long value) {
		Node node=new Node(value);
		if(isEmpty()) {
			last=node;
		}else {
			first.previous=node;
		}
		node.next=first;
		first=node;
	}
	//插入一个节点，在头结点后进行插入
	public void insertLast(long value) {
		Node node=new Node(value);
		if(isEmpty()) {
			first=node;
		}else {
			last.next=node;
			node.previous=last;
		}
		last=node;
	}
	
	//删除一个节点，在头结点后进行删除
	public Node deleteFirst() {
		Node temp=first;
		if(first.next==null) {
			last=null;
		}else {
			first.next.previous=null;
		}
		first=temp.next;
		return temp;
	}
	//删除一个节点，在尾2结点后进行删除
		public Node deleteLast() {
			Node temp=last;
			if(first.next==null) {
				first=null;
			}else {
				last.previous.next=null;
				
			}
			last=last.previous;
			return last;
		}
	//显示方法
	public void display() {
		Node current=first;
		while(current!=null) {
			current.display();
			current=current.next;
		}
		System.out.println();
	}
	//查找
	public Node find(long value) {
		Node current=first;
		while(current.data!=value) {
			if(current.next==null) {
				return null;
			}
			current=current.next;
		}
		return current;
	}
	//删除方法，根据数据域来进行删除
	public Node delete(long value) {
		Node current=first;
		Node previous=first;
		while(current.data!=value) {
			if(current.next==null) {
				return null;
			}
			previous=current;
			current=current.next;
		}
		if(current==first) {
			first=first.next;
		}else {
			current.previous.next=current.next;
		}
		return current;
	}
	//判断是否为空
	public boolean isEmpty() {
		return first==null;
	}
}
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

package chap05;

public class TestDoubleLinkList {
	public static void main(String[] args) {
		DoubleLinkList d=new DoubleLinkList();
		d.insertLast(10);
		d.insertLast(20);
		d.insertLast(30);
		d.display();
		
		d.deleteLast();
		d.display();
		
		d.deleteFirst();
		d.display();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

运行结果