Java中LinkedList的模擬實(shí)現(xiàn)
??關(guān)于LinkedList
LinkedList的底層是用一個(gè)雙向鏈表實(shí)現(xiàn)的，即一個(gè)結(jié)點(diǎn)中除了有一個(gè)引用指向下一個(gè)結(jié)點(diǎn)的地址，還有一個(gè)引用指向前一個(gè)結(jié)點(diǎn)的地址
LinkedList還有三個(gè)成員變量：
- ??size，表示該鏈表中結(jié)點(diǎn)的個(gè)數(shù)
- ??first，指向鏈表首結(jié)點(diǎn)
- ??last，指向鏈表尾結(jié)點(diǎn)
模擬實(shí)現(xiàn)LinkedList
??準(zhǔn)備工作
??創(chuàng)建靜態(tài)內(nèi)部類ListNode，后續(xù)創(chuàng)建結(jié)點(diǎn)都需要ListNode來創(chuàng)建新的結(jié)點(diǎn)
private static class ListNode<E> {
ListNode<E> pre; //指向前一個(gè)結(jié)點(diǎn)
ListNode<E> next; //指向下一個(gè)結(jié)點(diǎn)
E val; //結(jié)點(diǎn)的值
public ListNode(E val){
this.val = val;
}
}??創(chuàng)建成員變量：first，last，size
private ListNode<E> first; //指向鏈表首結(jié)點(diǎn)
private ListNode<E> last; //指向鏈表尾結(jié)點(diǎn)
private int size; //鏈表結(jié)點(diǎn)的個(gè)數(shù)??重寫toString()方法，在進(jìn)行測(cè)試方法的時(shí)候需要將鏈表打印出來
@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é)點(diǎn)，這里分兩種情況：鏈表為空，鏈表不為空
??鏈表為空：直接將first，last指向該結(jié)點(diǎn)，因?yàn)檫@個(gè)結(jié)點(diǎn)既是第一個(gè)結(jié)點(diǎn)，也是最后一個(gè)結(jié)點(diǎn)
??鏈表不為空：將first的pre執(zhí)行該結(jié)點(diǎn)，再將該結(jié)點(diǎn)的next指向first，更新first位置
??在結(jié)點(diǎn)頭插完后，更新size的長(zhǎng)度，進(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)行測(cè)試：依次頭插入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é)果：因?yàn)槭穷^插，所以打印4，3，2，1
尾插
- ??在鏈表的尾部插入結(jié)點(diǎn)，分兩種情況：鏈表為空，鏈表不為空
- ??鏈表為空：直接將first，last指向該結(jié)點(diǎn)，該結(jié)點(diǎn)既是鏈表的首結(jié)點(diǎn)，又是最后一個(gè)結(jié)點(diǎn)
- ??鏈表不為空：last的next執(zhí)行該節(jié)點(diǎn)，該節(jié)點(diǎn)的pre指向last，更新last位置
- ??在結(jié)點(diǎn)尾插完后，更新size的長(zhǎng)度，進(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)行測(cè)試：依次尾插入1，2，3，4，打印list
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(4);
System.out.println(list);??打印結(jié)果：因?yàn)槭俏膊?，所以打?，2，3，4
??在任意位置插入
這里分三種情況討論：在第一個(gè)位置插入，在最后一個(gè)位置插入，在其他位置插入
??在第一個(gè)位置插入：相當(dāng)于頭插，調(diào)用addFirst()方法
??在最后一個(gè)位置插入：相當(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)行測(cè)試：原來鏈表為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
這里分為三種情況：刪除的是第一個(gè)元素，刪除的是最后一個(gè)元素，刪除其他元素
- ??刪除一個(gè)元素：將first指向first的next，再將first的pre指向null
- ??刪除最后一個(gè)元素：將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)行測(cè)試：原鏈表為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
這個(gè)與刪除一次出現(xiàn)元素e的做法差不多，只是在找到第一次出現(xiàn)元素e時(shí)，將它刪掉，繼續(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)行測(cè)試：鏈表為1，2，1，3，1，將所有的1全部刪掉
list.removeAll(1);
System.out.println(list);??打印結(jié)果：鏈表中的元素只剩下2，3
找元素下標(biāo)indexOf
創(chuàng)建一個(gè)下標(biāo)index，從0開始增加，每遍歷一個(gè)元素進(jìn)行index++，如果遍歷的元素是要找的元素則返回index，當(dāng)遍歷完鏈表沒有要找的元素時(shí)，返回-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)行測(cè)試：鏈表為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
這個(gè)從鏈表尾部往前遍歷，創(chuàng)建index值為size-1，當(dāng)元素不為我們要找的元素時(shí)，index--，找到返回index，當(dāng)遍歷完整個(gè)鏈表都沒有找到時(shí)，返回-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)行測(cè)試：鏈表為1，2，3，3，4，5，找3的位置和6的位置
System.out.println(list.lastIndexOf(3));
System.out.println(list.lastIndexOf(6));??打印結(jié)果：最后一個(gè)3的下標(biāo)為3，6不在該鏈表中
??判斷鏈表是否包含某個(gè)元素
這里可以調(diào)用indexOf方法，看返回的是不是-1，如果不是-1則說明鏈表包含該元素，如果返回的是-1，說明鏈表不包含該元素
public boolean contains(E e){
return -1 != indexOf(e);
}??進(jìn)行測(cè)試：鏈表為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不在鏈表中
獲得鏈表長(zhǎng)度
直接返回size即可
public int size(){
return size;
}??進(jìn)行測(cè)試：返回空鏈表的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)行測(cè)試：看有元素的鏈表是否為空，和空鏈表是否為空
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)行測(cè)試：執(zhí)行清空操作，打印list
list.clear();
System.out.println(list);??打印結(jié)果：鏈表中沒有元素
到此這篇關(guān)于Java中LinkedList的模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java中 LinkedList的模擬內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Spring?Boot整合持久層之JdbcTemplate多數(shù)據(jù)源
持久層是JavaEE中訪問數(shù)據(jù)庫(kù)的核心操作,SpringBoot中對(duì)常見的持久層框架都提供了自動(dòng)化配置，例如JdbcTemplate、JPA 等，MyBatis 的自動(dòng)化配置則是MyBatis官方提供的。接下來分別向讀者介紹Spring Boot整合這持久層技術(shù)中的整合JdbcTemplate2022-08-08
本文主要講解了java 排序算法之選擇排序，選擇排序是最簡(jiǎn)單直觀的一種算法，想要了解相關(guān)知識(shí)的朋友快來看一看這篇文章吧2021-09-09
Spring Boot + Mybatis多數(shù)據(jù)源和動(dòng)態(tài)數(shù)據(jù)源配置方法
最近做項(xiàng)目遇到這樣的應(yīng)用場(chǎng)景，項(xiàng)目需要同時(shí)連接兩個(gè)不同的數(shù)據(jù)庫(kù)A, B，并且它們都為主從架構(gòu)，一臺(tái)寫庫(kù)，多臺(tái)讀庫(kù)。下面小編給大家?guī)砹薙pring Boot + Mybatis多數(shù)據(jù)源和動(dòng)態(tài)數(shù)據(jù)源配置方法，需要的朋友參考下吧2018-01-01
Spring Boot整合web層實(shí)現(xiàn)過程詳解
這篇文章主要介紹了Spring Boot整合web層實(shí)現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了詳解Maven多模塊打包遇到的問題解決方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
詳解最簡(jiǎn)單易懂的Spring Security 身份認(rèn)證流程講解
這篇文章主要介紹了詳解最簡(jiǎn)單易懂的Spring Security 身份認(rèn)證流程講解，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-03-03
這篇文章主要介紹了Java?BitMap源碼仿寫實(shí)現(xiàn)，所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個(gè)數(shù)據(jù)存不存在的2022-12-12
基數(shù)排序簡(jiǎn)介及Java語(yǔ)言實(shí)現(xiàn)
這篇文章主要介紹了基數(shù)排序簡(jiǎn)介及Java語(yǔ)言實(shí)現(xiàn)，涉及基數(shù)排序的基本思想簡(jiǎn)單介紹和桶排序的分析，以及基數(shù)排序的Java實(shí)現(xiàn)，具有一定借鑒價(jià)值，需要的朋友可以參考下。2017-11-11
下面小編就為大家分享一篇淺談Slf4j與其他日志系統(tǒng)兼容的使用方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2017-12-12
Java?NIO?Buffer實(shí)現(xiàn)原理詳解
本篇文章主要對(duì)NIO核心三件套：緩沖區(qū)(Buffer)、選擇器?(Selector)和通道(Channel)，其中之一的緩沖區(qū)Buffer實(shí)現(xiàn)原理的學(xué)習(xí)總結(jié)。感興趣的小伙伴可以了解一下2021-11-11