数据结构 -- 双向链表 linkedList 手写

1
2
3

双向链表 linkedList

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
package list;
public class LinkedList<E> {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
public void
add(E e){
linkedLast(e);
size++;
}
private void linkedLast(E e) {
// TODO Auto-generated method stub
Node<E> newNode = new Node<E>(last, e, null);
System.out.println("e=="+e);
//先保存起来last
Node<E> l = last;
//将最后一个last指向新元素
last = newNode;
//当last为空时 first指向元素 否则 将最后一个元素的next 指向新节点
if (l ==null) {
first = newNode;
}else{
l.next = newNode;
}
}
/**
* 在任意位置添加元素
* @param index
* @param e
*/
public void
add(int index,E e){
if (index<0 || index >size || e == null) {
return;
}
//当是在尾部添加元素时
if (index == size) {
linkedLast(e);
}else{
Node<E> p = node(index);
//当时在头部添加元素时
if (index == 0) {
Node<E> newNode = new Node<E>(null, e, p);
p.prev = newNode;
first = newNode;
}else{
//找到index节点的p的prev节点
Node<E> pp = p.prev;
//创建要添加的e的节点对象	并将它的前节点和后节点设置
Node<E> newNode = new Node<E>(pp, e, p);
//将前一个节点的下一个节点指向新节点
pp.next = newNode;
//将原来p节点的上一个节点设置给新节点
p.prev = newNode;
}
}
size++;
}
public void remove(int index) {
Node<E> target = node(index);
unlinked(target);
size --;
}
private void unlinked(Node<E> p){
//当是顶点节点时
if (p.prev == null) {
first = p.next;
}else{
p.prev.next = p.next;
}
//当时尾部节点时
if (p.next == null) {
last = p.prev;
}else{
p.next.prev = p.prev;
}
}
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;
}
}
public E get(int index) {
if (index<0 || index >size) {
return null;
}
return node(index).item;
}
private Node<E> node(int index) {
// TODO Auto-generated method stub
//优化算法
if (index < (size>>1)) {
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}else{
Node<E> node1 = last;
for (int i = size -1; i > index; i--) {
node1 = node1.prev;
}
return node1;
}
}
}
测试代码
复制代码package list;
public class TestMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("aaaa");
linkedList.add("bbbb");
linkedList.add("cccc");
linkedList.add(0,"dddd");
linkedList.add(1,"eeee");
for (int i = 0; i < linkedList.size; i++) {
System.out.print(linkedList.get(i)+"--"+linkedList.get(i+1)+"
");
}
System.out.println();
linkedList.remove(0);
for (int i = 0; i < linkedList.size; i++) {
System.out.print(linkedList.get(i)+"--"+linkedList.get(i+1)+"
");
}
}
}
package list;
public class TestMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("aaaa");
linkedList.add("bbbb");
linkedList.add("cccc");
linkedList.add(0,"dddd");
linkedList.add(1,"eeee");
for (int i = 0; i < linkedList.size; i++) {
System.out.print(linkedList.get(i)+"--"+linkedList.get(i+1)+"
");
}
System.out.println();
linkedList.remove(0);
for (int i = 0; i < linkedList.size; i++) {
System.out.print(linkedList.get(i)+"--"+linkedList.get(i+1)+"
");
}
}
}


复制代码