Java中LinkedList的模擬實現(xiàn)
??關(guān)于LinkedList
LinkedList的底層是用一個雙向鏈表實現(xiàn)的，即一個結(jié)點中除了有一個引用指向下一個結(jié)點的地址，還有一個引用指向前一個結(jié)點的地址
LinkedList還有三個成員變量：
- ??size，表示該鏈表中結(jié)點的個數(shù)
- ??first，指向鏈表首結(jié)點
- ??last，指向鏈表尾結(jié)點
模擬實現(xiàn)LinkedList
??準備工作
??創(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()方法，在進行測試方法的時候需要將鏈表打印出來
@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的長度，進行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++;
}??進行測試：依次頭插入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的長度，進行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++;
}??進行測試：依次尾插入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：下標越界");
}
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;
}??進行測試：原來鏈表為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
??刪除其他位置元素：參照下圖解析
??刪除完后，進行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--;
}??進行測試：原鏈表為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;
}
}??進行測試：鏈表為1，2，1，3，1，將所有的1全部刪掉
list.removeAll(1);
System.out.println(list);??打印結(jié)果：鏈表中的元素只剩下2，3
找元素下標indexOf
創(chuàng)建一個下標index，從0開始增加，每遍歷一個元素進行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;
}??進行測試：鏈表為1，2，3，4，5，找3的位置和6的位置
System.out.println(list.indexOf(3));
System.out.println(list.indexOf(6));??打印結(jié)果：3在下標為2的位置，6不在該鏈表中，故返回-1
??找元素下標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;
}??進行測試：鏈表為1，2，3，3，4，5，找3的位置和6的位置
System.out.println(list.lastIndexOf(3));
System.out.println(list.lastIndexOf(6));??打印結(jié)果：最后一個3的下標為3，6不在該鏈表中
??判斷鏈表是否包含某個元素
這里可以調(diào)用indexOf方法，看返回的是不是-1，如果不是-1則說明鏈表包含該元素，如果返回的是-1，說明鏈表不包含該元素
public boolean contains(E e){
return -1 != indexOf(e);
}??進行測試：鏈表為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;
}??進行測試：返回空鏈表的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;
}??進行測試：看有元素的鏈表是否為空，和空鏈表是否為空
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;
}??進行測試：執(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)文章
解決ResourceBundle.getBundle文件路徑問題
這篇文章主要介紹了解決ResourceBundle.getBundle文件路徑問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
本篇文章主要介紹了深度剖析java中JDK動態(tài)代理機制 ，動態(tài)代理避免了開發(fā)人員編寫各個繁鎖的靜態(tài)代理類，只需簡單地指定一組接口及目標類對象就能動態(tài)的獲得代理對象。2017-04-04
k8s部署springboot實現(xiàn)前后端分離項目
本文主要介紹了k8s部署springboot實現(xiàn)前后端分離項目,主要包括配置文件、鏡像構(gòu)建和容器編排等方面,具有一定的參考價值,感興趣的可以了解一下2024-01-01
Java并發(fā)編程之柵欄(CyclicBarrier)實例介紹
這篇文章主要介紹了Java并發(fā)編程之柵欄(CyclicBarrier)實例介紹,柵欄類似閉鎖,但是它們是有區(qū)別的,需要的朋友可以參考下2015-04-04
這篇文章主要為大家介紹了RabbitMq如何做到消息的可靠性投遞，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09
這篇文章主要介紹了一些常用排序算法整理，插入排序算法、直接插入排序、希爾排序、選擇排序、冒泡排序等排序,需要的朋友可以參考下2021-07-07
SpringCloud?Feign實現(xiàn)微服務(wù)之間相互請求問題
Feign是Netflix開發(fā)的聲明式、模板化的HTTP客戶端，?Feign可以幫助我們更快捷、優(yōu)雅地實現(xiàn)微服務(wù)之間的調(diào)用，這篇文章主要介紹了SpringCloud?Feign實現(xiàn)微服務(wù)之間相互請求,需要的朋友可以參考下2022-06-06
這篇文章主要為大家介紹了gRPC實踐之proto及Maven插件概念及使用詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
下面小編就為大家?guī)硪黄赥CP通信丟包原因總結(jié)(推薦)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
Java 采用反射獲取class屬性值的實現(xiàn)代碼
以下是對在Java中采用反射獲取class屬性值的實現(xiàn)代碼進行了分析介紹，需要的朋友可以過來參考下2013-08-08