¶写一个链表
¶一.概述
前面已经了解了 Collection 中一些常用数据结构的实现，现在实现简单版本的链表系列结构，包括单链表，双链表，循环链表，以此为基础构建不同类型的队列数据结构。
¶二.单链表
单链表的数据结构特点是元素存储有序，增删效率高，存储可以物理不连续
实现的基础可以是具备 next 的Node 结构，Node 是一个自包含的结构
Node:
用 java 实现一个简单的 Node 类 ：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19//实现比较简单
public class Node<E>{
//代表Node值的E
E e;
//代表下一个节点的next
Node next;
//无参构造
public Node(){}
//不指定next节点的构造
public Node(E e){
this.e=e;
this.next=null;
}
//指定next节点的构造
public Node(E e,Node next){
this.e=e;
this.next=next;
}
}- 主要需要实现值存储和持有后续节点引用
- 这里提供了三个构造函数，其实不指定使用默认构造也可以
SingleLinkedList :
结合上面的类实现单链表的数据结构 :
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
121public class SingleLinkedList<E>{
//持有头节点
Node<E> first;
//持有尾节点
Node<E> last;
//节点数量
int size;
//构造方法
public SingleLinkedList(){}
public SingleLinkedList(Node<E> first){
this.first=first;
this.last=first;
}
//先从添加元素开始
void insert(E e){
//先获取尾节点
Node<E> old = last;
//构造新的尾节点
last = new Node();
last.e = e;
last.next=null;
//这种情况表示空链表
if(size == 0){
first = last;
}else{
//链表非空，链接至链表尾
old.next = last;
}
size++;
}
//清空链表
void clear(){
first.e=null;
first.next=null;
first=null;
last=first;
size=0;
}
//移除元素的方法
void remove(){
if(size==0){
throw Exception("no element can be remove");
}else if(size == 1){
clear();
}else{
//将尾节点置空，size递减，原本的倒数第二个节点指向null，也就是作为新的尾节点存在
last.e = null;
last=null;
afterRemove();
size--;
}
}
//删除指定节点
void remove(E e){
for(Node<E> node;node !=null;node=node.next){
if(node.next.e.equals(e)){
if(null != node.next.next){
Node delNext = node.next.next;
node.next = delNode;
node.next.next=null;
return;
}else if(null == node.next.next){
remove();
}
}
}
}
//因为是单链表，需要改变last的引用
private void afterRemove(){
if(size==1){
last.e =first.e;
last = first;
return;
}
for(Node<E> node = first;node != null;node = node.next){
if(null==node.next){
last.e=node.e;
last = node;
}
}
}
//遍历
Node<E> forEach(E e){
if(size==0){
return null;
}
for(Node<E> node=first;node!=null;node=node.next){
if(node.e.equals(e)){
return node;
}else if(null == node.next && !node.e.equals(e)){
return null;
}
}
}
//获取指定元素
Node<E> get(E e){
return forEach(e);
}
//
E getFirst(){
if(size == 0){
return null;
}
return first.e;
}
//
E getLast(){
if(size==0){
return null;
}
return last;
}
}- 删除节点的方法比较粗糙，而且由于是单链表的结构，只有向后引用，所以预先判断了
next.next节点的状态 - 接下来改造出一个双链表
双链表:
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
122class DoubleLink{
//同样需要一个Node类,构造具备前后节点引用的节点
class Node<E>{
Node<E> prev;
Node<E> next;
E e;
}
//双链表的头,尾节点
Node<E> head;
Node<E> tail;
//size
private int size;
pubic DoubleLink(){
this.size = 0;
}
//尾插节点
public Node<E> tailAddNode(E e){
Node<E> newNode = Node<>();
neNode.e = e;
if(isEmpty()){
newNode.next=null;
newNode.prev=null;
head = newNode;
tail = newNode;
}else{
Node<E> oldLast = tail;
oldLast.next=newNode;
newNode.next=null;
newNode.prev=oldLast;
tail=newNode;
}
size++;
}
//头插节点
public void headAddNode(E e){
Node<E> newNode = new Node<>();
newNode.e=e;
if(isEmpty()){
newNode.next=null;
newNode.prev=null;
head = newNode;
tail = newNode;
}else{
Node<E> oldFirst = head;
oldFirst.prev=newNode;
newNode.prev=null;
newNode.next=olFirst;
tail=newNode;
}
size++;
}
//检查是否是空链表
private boolean isEmpty(){
if(size==0 && head == null && tail == null && head.equals(tail)){
return true;
}
return false;
}
//获取指定位置的节点值
public E get(int index){
Node need;
if(index >= size){
throw new IndexOutOfBoundException();
}else{
int count =0;
for(need = head; need!=null ;need=need.next){
count++;
if(count == index){
//遍历到了指定位置，跳出循环
break;
}
}
}
return need.e;
}
//删除节点
public Node remove(E e){
Node node;
if(isEmpty()){
throw new NullPointerException();
}else if(node.equals(head)){
Node first = head;
Node second = first.next;
second.prev=null;
first.next=null;
first=null;
head=second;
break;
}
for(node = head;node!=null;node=node.next){
if(node.e.equals(e)){
if(node.equals(head)){
Node first = head;
Node second = first.next;
second.prev=null;
first.next=null;
first=null;
head=second;
break;
}else{
//TODO
}
}
}
size--;
}
return node;
}
}