1 /**自己实现linkedlsit
2 * 添加 addFirst(E e) addLast(E e) add(E e) add(int index,E e)
3 * 获取 get(int index) getLast() getFirst()
4 * 删除 removeFirst() remvoeLast() remove() remove(int index) remove(Object o)
5 * @author cuiyc
6 * @version 1.0
7 * @date 2021/6/5 10:22
8 */
9 public class LinkedListDemo2 {
10 /**
11 * list的长度
12 */
13 private int size=0;
14 /**
15 * linkedlist的首节点
16 */
17 private Node first;
18 /**
19 * linkedlist的末尾节点
20 */
21 private Node last;
22
23 /**
24 * 定义一个静态内部类，即节点，包含前节点、元素、后节点
25 * @param 泛型参数
26 */
27 private static class Node{
28 E e;
29 Node prev;
30 Node next;
31
32 public Node(Node prev,E e,Node next){
33 this.e=e;this.prev=prev;this.next=next;
34 }
35 }
36
37 /**
38 * 空参构造函数
39 */
40 public LinkedListDemo2(){
41
42 }
43
44 /**
45 * 在linkedlist的头部添加元素
46 * @param e 要添加的元素
47 */
48 private void addFirst(E e){
49 //向linkedlist的头部添加元素
50 linkFirst(e);
51 }
52
53 /**
54 * 在linkedlist的尾部添加元素
55 * @param e 要添加的元素
56 */
57 private void addLast(E e){
58 //向linkedlist的尾部添加元素
59 linkLast(e);
60 }
61
62 /**
63 * 添加元素，默认是向linkedlist的尾部添加元素
64 * @param e 要添加的元素
65 */
66 private void add(E e){
67 addLast(e);
68 }
69
70 /**
71 * 向linkedlist的某个位置添加元素
72 * @param index linkedlist的某个位置
73 * @param e 要添加的元素
74 */
75 private void add(int index,E e){
76 //1 判断index是否和目前linkedlist的长度相等，如果相等，则表示需要添加到链表的尾部，否则是添加到尾部之前的其他位置
77 if(index==size){
78 linkLast(e);
79 }else {
80 linkBefore(index,e);
81 }
82 }
83
84 /**
85 * 获取linkedlist的最后一个节点的元素
86 * @return
87 */
88 private E getLast(){
89 final Node l=last;
90 if(l==null){
91 throw new NoSuchElementException();
92 }
93 return l.e;
94 }
95
96 /**
97 * 获取linkedlist的第一个节点元素
98 * @return
99 */
100 private E getFirst(){
101 final Node f=first;
102 if(f==null){
103 throw new NoSuchElementException();
104 }
105 return f.e;
106 }
107
108 /**
109 * 获取某个位置的节点元素
110 * @param index 位置
111 * @return
112 */
113 private E get(int index){
114 final Node n=node(index);
115 if(n==null){
116 throw new NoSuchElementException();
117 }
118 return n.e;
119 }
120
121 /**
122 * 移除linkedlist中的第一个元素
123 */
124 private void removeFirst(){
125 //1 找到first
126 final Node f=first;
127 if(f==null){
128 throw new NoSuchElementException();
129 }
130 unLinkFirst(f);
131 }
132
133 /**
134 * 移除linkedlist的最后一个元素
135 */
136 private void removeLast(){
137 //1 找到last node
138 final Node l=last;
139 if(l==null){
140 throw new NoSuchElementException();
141 }
142 unLinkLast(l);
143 }
144
145 /**
146 * 移除linkedlist中的元素，模式是移除最后一个元素
147 */
148 private void remove(){
149 removeLast();
150 }
151
152 /**
153 * 移除linkedlist中的某个位置的元素
154 * @param index 位置
155 */
156 private void remove(int index){
157 final Node n=node(index);
158 unLink(n);
159 }
160
161 /**
162 * 移除linkedlist中的某个元素的置
163 * @param o 元素的值
164 * @return
165 */
166 private Boolean remove(Object o){
167 //如果元素的值为null 则循环判断链表，如果节点的值为null，则删除那个节点
168 if(o==null){
169 for (Node n=first;n!=null;n=n.next){
170 if(n.e==null){
171 unLink(n);
172 return true;
173 }
174 }
175 }else {
176 //如果元素的值不为null，则循环判断链表，如果节点的值等于当前元素的值，则删除当前节点。
177 for (Node n=first;n!=null;n=n.next){
178 if(o.equals(n.e)){
179 unLink(n);
180 return true;
181 }
182 }
183 }
184 return false;
185 }
186
187 /**
188 * 移除linkedlist中的某个节点
189 * @param n
190 */
191 private E unLink(Node n) {
192 //拿到当前节点的元素值
193 final E element=n.e;
194 //拿到当前节点的上一个节点prev
195 final Nodeprev=n.prev;
196 //拿到当前节点的下一个节点next
197 final Nodenext=n.next;
198 //判断当前节点的上一节点是否为空，如果为空 则下一节点为first节点 如果不为空，则上一个节点的下一节点为next。并将当前节点的前一节点置空
199 if(prev==null){
200 first=next;
201 }else {
202 prev.next=next;
203 n.prev=null;
204 }
205 //判断下一节点是否为空，如果为空，则上一节点为last节点 如果不为空 则当前节点的下一节点的上个节点是prev，并将当前节点的next置空
206 if(next==null){
207 last=prev;
208 }else {
209 next.prev=prev;
210 n.next=null;
211 }
212 //当前节点的元素置空
213 n.e=null;
214 //元素的长度减1
215 size--;
216 return element;
217 }
218
219
220 /**
221 * 移除linkedlist的最后一个元素的实现方法
222 * @param l
223 */
224 private E unLinkLast(Node l) {
225 //1 找到最后一个节点的元素
226 final E element=l.e;
227 //2 找到最后一个节点前的那个节点
228 final Node prev=l.prev;
229 //将最后一个节点的元素置空 最后一个节点的前一个节点指针置空 将倒数第二个节点数组为last节点
230 l.e=null;
231 l.prev=null;
232 last=prev;
233 //判断如果倒数第二个节点为空，则first也为空 如果不为空，则其next节点设置为空。
234 if(prev==null){
235 first=null;
236 }else {
237 prev.next=null;
238 }
239 size--;
240 return element;
241 }
242
243
244 private E unLinkFirst(Node f){
245 //1 拿到第一个节点的元素
246 final E element=f.e;
247 //拿到第二个节点
248 final Node next=f.next;
249 //将第一个节点的元素置空 第一个节点的next节点置空 再将next节点设置为first节点
250 f.e=null;
251 f.next=null;//有助于垃圾回收
252 first=next;
253 //判断next节点是否为空 如果为空，则last节点也为空，如果不为空，则将next的prev节点置为空。
254 if(next==null){
255 last=null;
256 }else {
257 next.prev=null;
258 }
259 size--;
260 return element;
261 }
262
263 /**
264 * 向linkedlist的头部添加元素的实现方法
265 * @param e 要添加的元素
266 */
267 private void linkFirst(E e){
268 //1 找到first节点
269 final Node f=first;
270 //2 创建要添加的新的node节点
271 final Node newNode=new Node<>(null,e,f);
272 //3 将要添加的新的node节点定义为first节点
273 first=newNode;
274 //4 判断之前的f即fist节点的有无，如果没有，表示添加的新的节点即是first节点也是last节点。如果之前有first节点，则将之前的
275 //first的节点的prev执行新的first节点。
276 if(f==null){
277 last=newNode;
278 }else {
279 f.prev=newNode;
280 }
281 size++;
282 }
283
284 /**
285 * 向linkedlist的尾部添加元素的实现方法
286 * @param e 要添加的元素
287 */
288 private void linkLast(E e){
289 //1 找到last节点
290 final Nodel=last;
291 //2 创建要添加的新的node节点，前一节点指向之前的last节点，后一节点指向null
292 final NodenewNode=new Node<>(l,e,null);
293 //3 将新创建的node节点定义为last节点
294 last=newNode;
295 //4 判断之前的定义的last节点l是否为空，如果为空，则表示之前没有节点存在，即新添加的元素即是first节点也是last节点
296 // 如果之前定义的last节点l不为空，则将其next节点指向新创建的节点
297 if(l==null){
298 first=newNode;
299 }else {
300 l.next=newNode;
301 }
302 size++;
303 }
304
305 /**
306 * 向linkedlist的除了尾部的其他位置添加元素
307 * @param index list的位置
308 * @param e 要添加的元素
309 */
310 private void linkBefore(int index,E e){
311 //1 通过index 在linkedlist中找到那个节点
312 final Node succ=node(index);
313 //2 找到succ的前一个节点pred节点
314 final Node pred=succ.prev;
315 //3 新建一个节点，元素是e 其下一节点是succ节点,上一个节点是pred节点
316 final Node newNode=new Node<>(pred,e,succ);
317 //4 通过index找到的那个节点，设置其prev节点为newNode节点。
318 succ.prev=newNode;
319 //5 判断之前的succ的prev节点，是否为空。如果为空，表示newNode将是first节点，否则pred的next节点为newNode
320 if(pred==null){
321 first=newNode;
322 }else {
323 pred.next=newNode;
324 }
325 //6 linkedlist的长度加1
326 size++;
327 }
328
329 /**
330 * 通过index来查询linkedlist中的某个元素。
331 * @param index
332 * @return
333 */
334 private Node node(int index) {
335 //判断 index是分布在linkedlsit链表的左半部分还是右半部分 size>>1 即是size右移1位，size的0.5倍
336 if(index<(size>>1)){
337 Node x=first;
338 for (int i = 0; i < index; i++) {
339 x=x.next;
340 }
341 return x;
342 }else {
343 Node x=last;
344 for (int i=size-1;i>size;i--){
345 x=x.prev;
346 }
347 return x;
348 }
349 }
350 }