如何實現Java中一個簡單的LinkedList

LinkedList與ArrayList都是List接口的具體實現類。LinkedList與ArrayList在功能上也是大體一致，但是因為兩者具體的實現方式不一致，所以在進行一些相同操作的時候，其效率也是有差別的。

對于抽象的數據結構——線性表而言，線性表分為兩種，一種是順序存儲結構的順序表，另一種是通過指針來描述其邏輯位置的鏈表。

針對于具體的Java實現：

1. 順序存儲的順序表是用數組來實現的，以數組為基礎進行封裝各種操作而形成的List為ArrayList
2. 鏈表是用指針來描述其邏輯位置，在Java中以雙向鏈表為基礎進行封裝各種操作而形成的List為LinkedList

針對插入與刪除操作，ArrayList每插入一個元素，首先需要判斷數組的空間夠不夠，不夠要進行擴容，在有足夠的空間的基礎上，在指定的index位置上插入元素，但是該index及以后的元素都要后移。雖然刪除操作不需要判斷空間夠不夠，但同樣需要該index及以后的元素向前移動，這些移動的操作會增加時間的復雜度。但是對于LinkedList就不一樣，因為使用指針來指示其邏輯的位置，所以插入與刪除的操作的時間復雜度都是 ** O(1) **

雖然對于ArrayList而言，插入與刪除的時間復雜度很高，但是對于查找指定位置的元素這種操作而言，就非常的快，因為可以通過數組直接得到該下標對應的元素。反而，LinkedList而言，無法直接返回指定位置的元素，需要一個個查詢，其時間的復雜度就是 ** O(n) **

與如何實現Java的ArrayList經典實體類一樣，實現的目的主要在于練手以及掌握官方實現的原理和一些技巧，因此很多需要與其他類配合的方法和功能，就先不在這里實現如iterator等

所以，實現的LinkedList的方法如下：

add方法

get方法

indexOf方法

remove方法

與實現ArrayList的名字一樣，為SimpleLinkedList。源碼地址，歡迎star,fork

構建一個雙向鏈表

構建的代碼如下：

 private static class Node<E>{
 E item;
 Node<E> next;
 Node<E> prev;
 public Node(E item, Node<E> next, Node<E> prev) {
 this.item = item;
 this.next = next;
 this.prev = prev;
 }
 } 

常規的雙向鏈表的構建方法，一個數字域存放數組，一個前指針指向一個Node類型的元素，一個后指針指向一個Node類型的元素。

對于LinkedList的實現而言，還需要以下三個成員變量

 private int size;
 private Node<E> first;
 private Node<E> last;

Add方法

這里實現的add方法是簡單的add(E e)以及add(int index,E e)兩個方法，addAll()將其他集合轉換LinkedList的方法，暫時放到以后去實現。

add方法兩個重載方法，其分別對應不同的添加方式。先說add(E e)方法的實現。

 public boolean add(E element) {
 addAtLast(element);
 return true;
 }

不指定位置添加元素，則默認添加到了鏈表的最后。addAtLast的核心代碼如下：

 private void addAtLast(E element) {
 Node<E> l = last;
 Node<E> node = new Node<E>(element, null, l);
 last = node;
 if (l == null) {
 first = node;
 } else {
 l.next = node;
 }
 size++;
 }

首先找到最后一位的Node元素，然后根據element創建一個新的Node元素，其next指向為null,prev指向為最后一位Node元素。在創建完Node元素之后，last就變成了先創建的Node元素，接下來只需要把新node元素加到鏈表中即可。即讓l對象(原最后一位，現倒數第二位元素的next指針，指向新node元素)。至此，新node元素的next指向null,prev指向倒數第二個元素，倒數第二個元素的next指向新node，就將node成功加入鏈表。

上述的操作也可以看出，其插入的操作非常省時間，比起ArrayList，擴容，移動元素快很多。

add的第二個重載方法 add(int index ,E e),先看代碼實現：

 public void add(int index, E element) {
 checkRangeForAdd(index);
 if (index == size) {
 addAtLast(element);
 } else {
 Node<E> l = node(index);
 addBeforeNode(element, l);
 }
 }

首先判斷要插入的index是否在范圍內，在的話，再執行后續的add操作。如果要插入的index剛好是最后一位，則執行上面講的addAtLast，如果不是，則得到index所對應的Node元素，執行addBeforeNode。

獲取index所對應的Node元素，是node方法，代碼如下：

 private Node<E> node(int index) {
 if (index < (size << 1)) {
 Node<E> cursor = first;
 for (int i = 0; i < index; i++) {
 cursor = cursor.next;
 }
 return cursor;
 } else {
 Node<E> cursor = last;
 for (int i = size - 1; i > index; i--) {
 cursor = cursor.prev;
 }
 return cursor;
 }
 }

這里的查找采用二分查找，節省查找時間，而且也應用到了雙向鏈表的特點。首先判斷index在前一半的范圍內，還是后一半的范圍內。如果是前一半，則游標Node初始為first,用游標Node元素的next，不斷指向index所在的元素。如果是后一半，則游標Node初始為last,用游標Node元素的prev,不斷指向index所在的元素。

在指定元素的前面插入新節點的addBeforeNode的方法如下：

 private void addBeforeNode(E element, Node<E> specifiedNode) {
 Node<E> preNode = specifiedNode.prev;
 Node<E> newNode = new Node<>(element, specifiedNode, preNode);
 if (preNode == null) {
 first = newNode;
 } else {
 preNode.next = newNode;
 }
 specifiedNode.prev = newNode;
 size++;
 }

插入的方式很簡單，新節點的prev是原index元素的prev,新節點的next是原index元素。剩下的操作是把該node放到鏈表中，讓原index元素的prev的next為新節點，但是要判斷preNode是不是空，是的話，表示newNode為第一個元素，就是first。

至此，一個add方法，就實現完了。

get方法

get方法在有了上述node方法之后，就非常的簡單。代碼如下：

 public E get(int index) {
 checkRange(index);
 return node(index).item;
 }

checkRange檢查index是否不在范圍內。

 private void checkRange(int index) {
 if (index >= size || index < 0) {
 throw new IndexOutOfBoundsException("指定index超過界限");
 }
 }

indexOf方法

indexOf(Object o)用來得到指定元素的下標。

 public int indexOf(Object element) {
 Node<E> cursor = first;
 int count = 0;
 while (cursor != null) {
 if (element != null) {
 if (element.equals(cursor.item)) {
  return count;
 }
 }else{
 if (cursor.item == null) {
  return count;
 }
 }
 count ++;
 cursor = cursor.next;
 }
 return -1;
 }

與ArrayList一樣，從第一位開始查找，首先先判斷element是不是null,分成兩種情況。

remove方法

remove方法與add方法一樣，同樣有兩個重載的方法，remove(Object o)與remove(int index)

先看簡單的remove(int index)方法，代碼如下：

 public E remove(int index) {
 checkRange(index);
 return deleteLink(index);
 }

deleteLink是將該index所對應的節點的鏈接刪除的方法，其代碼如下：

 private E deleteLink(int index) {
 Node<E> l = node(index);
 E item = l.item;
 Node<E> prevNode = l.prev;
 Node<E> nextNode = l.next;
 if (prevNode == null) {
 first = nextNode;
 }else{
 prevNode.next = nextNode;
 l.next = null;
 }
 if (nextNode == null) {
 last = prevNode;
 }else{
 nextNode.prev = prevNode;
 l.prev = null;
 }
 size--;
 l.item = null;
 return item;
 }

首先獲得該index對應的Node元素，得到該Node元素的前一個元素和后一個元素。接下來，只需要將前一個元素和后一個元素直接相連即可，其他只需要額外判斷前一個元素和后一個元素是否為null就行。在判斷前一個元素是否為null的時候，只需要操作前一個元素，在判斷后一個元素是否為null的時候，也只需要操作后一個元素。最后，將要刪除的元素各個引用至為null。

remove另一個重載方法remove(Object o)，在實現了indexOf和deleteLink方法之后，就非常簡單。

 public boolean remove(Object o) {
 int index = indexOf(o);
 if (index < 0){
 return false;
 }
 deleteLink(index);
 return true;
 }

獲取該元素對應對應的下標，然后執行deleteLink方法，完成remove操作。

總結

至此，一個功能簡單的LinkedList就實現完成了，全部的代碼可以看源碼地址，

以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持億速云！