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
??在任意位置插入
這里分三種情況討論：在第一個位置插入，在最后一個位置插入，在其他位置插入
??在第一個位置插入：相當于頭插，調(diào)用addFirst()方法
??在最后一個位置插入：相當于尾插，調(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，當遍歷完鏈表沒有要找的元素時，返回-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，當元素不為我們要找的元素時，index--，找到返回index，當遍歷完整個鏈表都沒有找到時，返回-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)文章
Spring?Boot整合持久層之JdbcTemplate多數(shù)據(jù)源
持久層是JavaEE中訪問數(shù)據(jù)庫的核心操作,SpringBoot中對常見的持久層框架都提供了自動化配置，例如JdbcTemplate、JPA 等，MyBatis 的自動化配置則是MyBatis官方提供的。接下來分別向讀者介紹Spring Boot整合這持久層技術(shù)中的整合JdbcTemplate2022-08-08
本文主要講解了java 排序算法之選擇排序，選擇排序是最簡單直觀的一種算法，想要了解相關(guān)知識的朋友快來看一看這篇文章吧2021-09-09
Spring 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 Boot整合web層實現(xiàn)過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了詳解Maven多模塊打包遇到的問題解決方法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
詳解最簡單易懂的Spring Security 身份認證流程講解
這篇文章主要介紹了詳解最簡單易懂的Spring Security 身份認證流程講解，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-03-03
這篇文章主要介紹了Java?BitMap源碼仿寫實現(xiàn)，所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據(jù)存不存在的2022-12-12
這篇文章主要介紹了基數(shù)排序簡介及Java語言實現(xiàn)，涉及基數(shù)排序的基本思想簡單介紹和桶排序的分析，以及基數(shù)排序的Java實現(xiàn)，具有一定借鑒價值，需要的朋友可以參考下。2017-11-11
下面小編就為大家分享一篇淺談Slf4j與其他日志系統(tǒng)兼容的使用方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12
本篇文章主要對NIO核心三件套：緩沖區(qū)(Buffer)、選擇器?(Selector)和通道(Channel)，其中之一的緩沖區(qū)Buffer實現(xiàn)原理的學(xué)習(xí)總結(jié)。感興趣的小伙伴可以了解一下2021-11-11