你未必出類拔萃，但一定與衆不同
手寫LinkedList實作基本功能
文章目錄
- 手寫LinkedList實作基本功能
-
- 概述
- 手寫内容
-
- 成員變量和常量
- Node節點
- add方法
- get方法
- set方法
- 越界問題
- remove方法
- clear方法
- 完整代碼
概述
LinkedList
主要 特性：
- 順序通路
- 寫快讀慢 讀的時候需要周遊 底層采用了折半查找提高了效率 但是比起數組來說還是慢的多
檢視源碼
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
AbstractSequentialList：該抽象類繼承自java.util.AbstractList 提供了順序通路存儲結構，隻要類似于linkedList這樣的順序通路List 都可以繼承該類
List：清單标準接口，清單是一個有序集合，又被稱為序列，該接口對内部的每一個元素的插入位置都有精确控制
Deque：雙向隊列接口，繼承自Queue 因為Queue是先進先出的特性 繼承後 就看可以在尾部增加資料頭部擷取資料
Cloneable：标記可克隆對象 ，沒有實作該接口的對象在調用Object.clone()方法時會抛出異常 分為淺拷貝和深拷貝 這裡預設都是淺拷貝
java.io.Serializable：序列化标記接口 被此接口标記的類 可以實作Java序列化和反序列化
手寫内容
成員變量和常量
- size标記序列的大小 統計節點的個數
- first 連結清單的頭結點
- last 連結清單的尾結點
/**
* 連結清單實際長度
*/
private int size;
/**
* 指向第一個節點 為了查詢開始
*/
private Node first;
/**
* 指向最後一個節點 為了插入開始
*/
private Node last;
這裡沒有和源碼一樣用transient修飾
transient修飾 的作用是 用于标記無需序列化的成員變量
也就是說 實作了 Serializable接口的LinkedList 一定提供了readObject和writeObject方法 源碼如下
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
/**
* Reconstitutes this {@code LinkedList} instance from a stream
* (that is, deserializes it).
*/
@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
// Read in size
int size = s.readInt();
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
Node節點
連結清單由節點構成 節點又包含 資料域 和指針域
prev 前指針
next 後指針
object就是資料域
class Node{
/**
* 前指針 指向上一個節點
*/
Node prev;
/**
* 後指針 指向下一個節點
*/
Node next;
Object object;
}
add方法
- 建立一個節點 将插入的資料給這個節點的資料域指派
- 判斷頭指針是否為空 為空則說明這個是頭指針 不為空則在尾部進行插入
- 然後讓這個節點為最後一個節點
- 連結清單長度+1
主要邏輯詳見注解
/**
* 添加資料進入
* @param e
*/
public void add(E e){
Node node = new Node();
node.object = e;
//如果第一個節點為空 就插入第一個資料
if(first == null){
//添加第一個元素給第一個元素指派
first = node;
}else{//插入第二個及其以上資料
node.prev = last;
//将上一個元素的節點的下一個指向node 此時node還不是last
last.next = node;
}
last = node;
size++;
}
/**
* 插入節點
* @param index
* @param e
*/
public void add(int index, E e) {
Node newNode = new Node();
newNode.object = e;
// 擷取原來的節點
Node oldNode = getNode(index);
// 擷取原來的上一個節點
Node oldNodePrev = oldNode.prev;
//将原來的節點的上一個節點為新節點
oldNode.prev = newNode;
if (oldNodePrev == null) {
first = newNode;
} else {
//上一個節點的下一個節點是新節點
oldNodePrev.next = newNode;
}
//新節點的下一個節點為原來節點
newNode.next = oldNode;
size++;
}
get方法
源碼是這樣寫的 采用折半查找進行資料的搜尋
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//源碼優化折半查找
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
我這裡簡單點 直接周遊查找擷取
/**
* 擷取元素值
* @param index
* @return
*/
public E get(int index) {
Node node = getNode(index);
return (E) node.object;
}
/**
* 得到節點
* @param index
* @return
*/
public Node getNode(int index) {
Node node = null;
if (first != null) {
node = first;
//源碼中采用折半查找 我們這裡是直接周遊
for (int i = 0; i < index; i++) {
node = node.next;
}
}
return node;
}
set方法
資料的修改
調用前面的擷取目前的節點的值get方法擷取 然後直接修改值即可
/**
* 修改資料
* @param index
* @param element
* @return
*/
public E set(int index, E element) {
checkElementIndex(index);
Node node = getNode(index);
E oldVal = (E) node.object;
node.object = element;
return oldVal;
}
越界問題
- 判斷是否越界 目前的索引必須大于0小于目前連結清單的長度
/**
* 檢查越界
* @param index
*/
private void checkElementIndex(int index) {
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException("下标越界");
}
}
/**
* 判斷參數是否是現有元素的索引
* @param index
* @return
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
remove方法
移除元素
- 判斷越界問題
- 拿到目前要移除的節點
- 拿到目前要移除節點的上一個節點和下一個節點 友善把這兩個節點連接配接在一塊
- 連接配接上一個節點和下一個節點 判斷邊界
- 長度減1
/**
* 删除元素
* @param index
* @return
*/
public Object remove(int index){
//檢查越界
checkElementIndex(index);
//擷取目前删除節點
Node node = getNode(index);
if (node != null) {
//得到目前删除節點的上一個節點
Node prevNode = node.prev;
//得到目前删除節點的下一個節點
Node nextNode = node.next;
// 設定上一個節點的next為目前删除節點的next
if (prevNode != null) {
prevNode.next = nextNode;
}
// 判斷是否是最後一個節點
if (nextNode != null) {
nextNode.prev = prevNode;
}
}
size--;
return node;
}
clear方法
- 循環清除整個連結清單
- 置為空後将垃圾回收交給垃圾回收器自己判斷清除
- 連結清單長度置為1
public void clear(){
//循環清除各個節點之間的聯系
for (Node x = first; x != null; ) {
Node next = x.next;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
}
完整代碼
import java.util.LinkedList;
/**
* @author Yu W
* @version V1.0
* @ClassName MyLinkedList
* @Description: 手寫LinkedList 學習LinkedList源碼
* @date 2021/7/18 18:00
*/
public class MyLinkedList <E> {
class Node{
/**
* 前指針 指向上一個節點
*/
Node prev;
/**
* 後指針 指向下一個節點
*/
Node next;
Object object;
}
/**
* 連結清單實際長度
*/
private int size;
/**
* 指向第一個節點 為了查詢開始
*/
private Node first;
/**
* 指向最後一個節點 為了插入開始
*/
private Node last;
/**
* 添加資料進入
* @param e
*/
public void add(E e){
Node node = new Node();
node.object = e;
//如果第一個節點為空 就插入第一個資料
if(first == null){
//添加第一個元素給第一個元素指派
first = node;
}else{//插入第二個及其以上資料
node.prev = last;
//将上一個元素的節點的下一個指向node 此時node還不是last
last.next = node;
}
last = node;
size++;
}
/**
* 修改資料
* @param index
* @param element
* @return
*/
public E set(int index, E element) {
checkElementIndex(index);
Node node = getNode(index);
E oldVal = (E) node.object;
node.object = element;
return oldVal;
}
/**
* 插入節點
* @param index
* @param e
*/
public void add(int index, E e) {
Node newNode = new Node();
newNode.object = e;
// 擷取原來的節點
Node oldNode = getNode(index);
// 擷取原來的上一個節點
Node oldNodePrev = oldNode.prev;
//将原來的節點的上一個節點為新節點
oldNode.prev = newNode;
if (oldNodePrev == null) {
first = newNode;
} else {
//上一個節點的下一個節點是新節點
oldNodePrev.next = newNode;
}
//新節點的下一個節點為原來節點
newNode.next = oldNode;
size++;
}
/**
* 擷取元素值
* @param index
* @return
*/
public E get(int index) {
Node node = getNode(index);
return (E) node.object;
}
/**
* 得到節點
* @param index
* @return
*/
public Node getNode(int index) {
Node node = null;
if (first != null) {
node = first;
//源碼中采用折半查找 我們這裡是直接周遊
for (int i = 0; i < index; i++) {
node = node.next;
}
}
return node;
}
/**
* 删除元素
* @param index
* @return
*/
public Object remove(int index){
//檢查越界
checkElementIndex(index);
//擷取目前删除節點
Node node = getNode(index);
if (node != null) {
//得到目前删除節點的上一個節點
Node prevNode = node.prev;
//得到目前删除節點的下一個節點
Node nextNode = node.next;
// 設定上一個節點的next為目前删除節點的next
if (prevNode != null) {
prevNode.next = nextNode;
}
// 判斷是否是最後一個節點
if (nextNode != null) {
nextNode.prev = prevNode;
}
}
size--;
return node;
}
/**
* 檢查越界
* @param index
*/
private void checkElementIndex(int index) {
if (!isElementIndex(index)) {
throw new IndexOutOfBoundsException("下标越界");
}
}
/**
* 判斷參數是否是現有元素的索引
* @param index
* @return
*/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 從此清單中删除所有元素。此調用傳回後，清單将為空
*/
public void clear(){
//循環清除各個節點之間的聯系
for (Node x = first; x != null; ) {
Node next = x.next;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)