Java中LinkedList的模擬實現(xiàn)
??關(guān)于LinkedList
LinkedList的底層是用一個雙向鏈表實現(xiàn)的,即一個結(jié)點中除了有一個引用指向下一個結(jié)點的地址,還有一個引用指向前一個結(jié)點的地址
LinkedList還有三個成員變量:
- ??size,表示該鏈表中結(jié)點的個數(shù)
- ??first,指向鏈表首結(jié)點
- ??last,指向鏈表尾結(jié)點
模擬實現(xiàn)LinkedList
??準(zhǔn)備工作
??創(chuàng)建靜態(tài)內(nèi)部類ListNode,后續(xù)創(chuàng)建結(jié)點都需要ListNode來創(chuàng)建新的結(jié)點
private static class ListNode<E> { ListNode<E> pre; //指向前一個結(jié)點 ListNode<E> next; //指向下一個結(jié)點 E val; //結(jié)點的值 public ListNode(E val){ this.val = val; } }
??創(chuàng)建成員變量:first,last,size
private ListNode<E> first; //指向鏈表首結(jié)點 private ListNode<E> last; //指向鏈表尾結(jié)點 private int size; //鏈表結(jié)點的個數(shù)
??重寫toString()方法,在進(jìn)行測試方法的時候需要將鏈表打印出來
@Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); if(first == null){ sb.append("]"); }else { ListNode<E> cur = first; while(cur.next != null){ sb.append(cur.val); sb.append(","); cur = cur.next; } sb.append(cur.val); sb.append("]"); } return sb.toString(); }
??頭插
??在鏈表的頭部插入結(jié)點,這里分兩種情況:鏈表為空,鏈表不為空
??鏈表為空:直接將first,last指向該結(jié)點,因為這個結(jié)點既是第一個結(jié)點,也是最后一個結(jié)點
??鏈表不為空:將first的pre執(zhí)行該結(jié)點,再將該結(jié)點的next指向first,更新first位置
??在結(jié)點頭插完后,更新size的長度,進(jìn)行size++
public void addFirst(E e){ ListNode<E> newNode = new ListNode<>(e); if(first == null){ first = newNode; last = newNode; }else { first.pre = newNode; newNode.next = first; first = newNode; } size++; }
??進(jìn)行測試:依次頭插入1,2,3,4,打印list
MyLinkedList<Integer> list = new MyLinkedList<>(); list.addFirst(1); list.addFirst(2); list.addFirst(3); list.addFirst(4); System.out.println(list);
??打印結(jié)果:因為是頭插,所以打印4,3,2,1
尾插
- ??在鏈表的尾部插入結(jié)點,分兩種情況:鏈表為空,鏈表不為空
- ??鏈表為空:直接將first,last指向該結(jié)點,該結(jié)點既是鏈表的首結(jié)點,又是最后一個結(jié)點
- ??鏈表不為空:last的next執(zhí)行該節(jié)點,該節(jié)點的pre指向last,更新last位置
- ??在結(jié)點尾插完后,更新size的長度,進(jìn)行size++
public void addLast(E e){ ListNode<E> newNode = new ListNode<>(e); if(first == null){ first = newNode; last = newNode; }else { last.next = newNode; newNode.pre = last; last = newNode; } size++; }
??進(jìn)行測試:依次尾插入1,2,3,4,打印list
list.addLast(1); list.addLast(2); list.addLast(3); list.addLast(4); System.out.println(list);
??打印結(jié)果:因為是尾插,所以打印1,2,3,4
??在任意位置插入
這里分三種情況討論:在第一個位置插入,在最后一個位置插入,在其他位置插入
??在第一個位置插入:相當(dāng)于頭插,調(diào)用addFirst()方法
??在最后一個位置插入:相當(dāng)于尾插,調(diào)用addLast()方法
??在其他位置插入:看下圖解析
public boolean addIndex(int index,E e){ ListNode<E> newNode = new ListNode<>(e); if(index < 0 && index > size){ throw new IndexOutOfBoundsException("addIndex:下標(biāo)越界"); } if(index == size){ addLast(e); }else if(index == 0){ addFirst(e); }else { ListNode<E> cur = first; for(int i = 0;i < index;i++){ cur = cur.next; } newNode.pre = cur.pre; newNode.next = cur; newNode.pre.next = newNode; cur.pre = newNode; size++; } return true; }
??進(jìn)行測試:原來鏈表為1,2,3,4,在位置0插入1,在位置5插入5,在位置3插入3
list.addIndex(0,1); list.addIndex(4,5); list.addIndex(3,3); System.out.println(list);
??打印結(jié)果:打印為1,1,2,3,3,4,5
??刪除remove
這里分為三種情況:刪除的是第一個元素,刪除的是最后一個元素,刪除其他元素
- ??刪除一個元素:將first指向first的next,再將first的pre指向null
- ??刪除最后一個元素:將last更新為last的pre位置,再將last的next指向null
??刪除其他位置元素:參照下圖解析
??刪除完后,進(jìn)行size--操作
public void remove(E e){ ListNode<E> cur = first; while(cur != null){ if(e.equals(cur.val)){ break; } cur = cur.next; } if(cur == first){ first = first.next; first.pre = null; }else if(cur == last){ last = last.pre; last.next = null; }else { cur.pre.next = cur.next; cur.next.pre = cur.pre; } size--; }
??進(jìn)行測試:原鏈表為1,2,3,4,5,刪除1,刪除5,刪除3
list.remove(1); list.remove(5); list.remove(3); System.out.println(list);
??打印結(jié)果:打印2,4
??刪除removeAll
這個與刪除一次出現(xiàn)元素e的做法差不多,只是在找到第一次出現(xiàn)元素e時,將它刪掉,繼續(xù)遍歷鏈表
public void removeAll(E e){ ListNode<E> cur = first; while(cur != null){ if(cur.val.equals(e)){ if(cur == first){ first = first.next; first.pre = null; }else if(cur == last){ last = last.pre; last.next = null; }else { cur.pre.next = cur.next; cur.next.pre = cur.pre; } size--; } cur = cur.next; } }
??進(jìn)行測試:鏈表為1,2,1,3,1,將所有的1全部刪掉
list.removeAll(1); System.out.println(list);
??打印結(jié)果:鏈表中的元素只剩下2,3
找元素下標(biāo)indexOf
創(chuàng)建一個下標(biāo)index,從0開始增加,每遍歷一個元素進(jìn)行index++,如果遍歷的元素是要找的元素則返回index,當(dāng)遍歷完鏈表沒有要找的元素時,返回-1
public int indexOf(E e){ ListNode<E> cur = first; int index = 0; while(cur != null){ if(e.equals(cur.val)){ return index; }else { index++; cur = cur.next; } } return -1; }
??進(jìn)行測試:鏈表為1,2,3,4,5,找3的位置和6的位置
System.out.println(list.indexOf(3)); System.out.println(list.indexOf(6));
??打印結(jié)果:3在下標(biāo)為2的位置,6不在該鏈表中,故返回-1
??找元素下標(biāo)lastIndexOf
這個從鏈表尾部往前遍歷,創(chuàng)建index值為size-1,當(dāng)元素不為我們要找的元素時,index--,找到返回index,當(dāng)遍歷完整個鏈表都沒有找到時,返回-1
public int lastIndexOf(E e){ ListNode<E> cur = last; int index = size-1; while(cur != null){ if(e.equals(cur.val)){ return index; }else { cur = cur.pre; index--; } } return -1; }
??進(jìn)行測試:鏈表為1,2,3,3,4,5,找3的位置和6的位置
System.out.println(list.lastIndexOf(3)); System.out.println(list.lastIndexOf(6));
??打印結(jié)果:最后一個3的下標(biāo)為3,6不在該鏈表中
??判斷鏈表是否包含某個元素
這里可以調(diào)用indexOf方法,看返回的是不是-1,如果不是-1則說明鏈表包含該元素,如果返回的是-1,說明鏈表不包含該元素
public boolean contains(E e){ return -1 != indexOf(e); }
??進(jìn)行測試:鏈表為1,2,3,4,5,判斷該鏈表是否包含2和6
boolean ret = list.contains(2); boolean ret1 = list.contains(6); System.out.println(ret); System.out.println(ret1);
??輸出結(jié)果:2在鏈表中,6不在鏈表中
獲得鏈表長度
直接返回size即可
public int size(){ return size; }
??進(jìn)行測試:返回空鏈表的size,和有元素的size
list.clear(); System.out.println(list.size()); list.addFirst(1); System.out.println(list.size());
??打印結(jié)果:
鏈表判空
判斷鏈表為空有兩種方式:判斷size是否為0或者判斷first是否指向null
public boolean isEmpty(){ //return size==0; return first==null; }
??進(jìn)行測試:看有元素的鏈表是否為空,和空鏈表是否為空
list.clear(); list.addFirst(1); boolean ret1 = list.isEmpty(); System.out.println(ret1); list.clear(); boolean ret2 = list.isEmpty(); System.out.println(ret2);
??打印結(jié)果:
清空鏈表
清空操作就是將first指向null,將last指向null,將size置0
public void clear(){ first = null; last = null; size = 0; }
??進(jìn)行測試:執(zhí)行清空操作,打印list
list.clear(); System.out.println(list);
??打印結(jié)果:鏈表中沒有元素
到此這篇關(guān)于Java中LinkedList的模擬實現(xiàn)的文章就介紹到這了,更多相關(guān)Java中 LinkedList的模擬內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Spring?Boot整合持久層之JdbcTemplate多數(shù)據(jù)源
持久層是JavaEE中訪問數(shù)據(jù)庫的核心操作,SpringBoot中對常見的持久層框架都提供了自動化配置,例如JdbcTemplate、JPA 等,MyBatis 的自動化配置則是MyBatis官方提供的。接下來分別向讀者介紹Spring Boot整合這持久層技術(shù)中的整合JdbcTemplate2022-08-08Spring Boot + Mybatis多數(shù)據(jù)源和動態(tài)數(shù)據(jù)源配置方法
最近做項目遇到這樣的應(yīng)用場景,項目需要同時連接兩個不同的數(shù)據(jù)庫A, B,并且它們都為主從架構(gòu),一臺寫庫,多臺讀庫。下面小編給大家?guī)砹薙pring Boot + Mybatis多數(shù)據(jù)源和動態(tài)數(shù)據(jù)源配置方法,需要的朋友參考下吧2018-01-01詳解最簡單易懂的Spring Security 身份認(rèn)證流程講解
這篇文章主要介紹了詳解最簡單易懂的Spring Security 身份認(rèn)證流程講解,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2019-03-03