資料結構之連結清單實作

分析：

連結清單（Linked list）是一種常見的基礎資料結構，是一種線性表，但是并不會按線性的順序存儲資料，而是在每一個節點裡存到下一個節點的指針(Pointer)。
單連結清單是連結清單中結構最簡單的。一個單連結清單的節點(Node)分為兩個部分，一個是資料域，一個是節點域。
雙向連結清單可以從兩個方向周遊

1. 單向連結清單

1）定義一個節點

class Node<E> {

    E e;
    Node<E> next;
    public Node(E e,Node<E> next){
        this.e = e;
        this.next = next;
    }

    public Node(E e){
        this(e,null);
    }
}

2）構造函數

//虛拟頭節點
private Node<E> dummyHead;
private int size;
public LinkedList(){
    dummyHead = new Node<>(null,null);
    size = ;
}

3）添加元素

//1->2->3->4
//1. 首先找到要插入位置的前節點
//2. 比如你要在index=2位置插入66，你就把要插入的66節點的next指向3，2的next節點指向66，然後就插入進去了
public void add(int index, E e){

    Node<E> pre = dummyHead;
    for (int i = ; i < index; i++)
        pre = pre.next;
    Node<E> node = new Node<>(e);
    //目前待插入節點的next用待插入節點的前一個節點的next指向
    node.next = pre.next;
    //前一個節點的next指向目前節點就對了
    pre.next = node;
    size++;
}

public void addFirst(E e){
    add(,e);
}

public void addLast(E e){
    add(size,e);
}

3）擷取資料

擷取資料就是擷取某一個位置的節點，然後就能擷取這個節點的資料了
public E get(int index){
    if(index <  || index > size){
        throw new IllegalArgumentException("角标不合法");
    }
    Node<E> current = dummyHead.next;
    for (int i = ; i < index; i++) {
        current = current.next;
    }
    return current.e;
}

public E getFirst(){
    return get();
}

public E getLast(){
    return get(size - );
}

4）修改資料

//首先找到要修改的index節點，然後直接修改
public void set(int index, E e){
    if(index <  || index > size){
        throw new IllegalArgumentException("角标不合法");
    }
    Node<E> current = dummyHead.next;
    for (int i = ; i < index; i++) {
        current = current.next;
    }
    current.e = e;
}

5) 删除資料

//1->2->3->4
//假設我要删除2這個節點 我就應該找到它的前一個節點1，然後
//用1這個節點指向要删除節點的下一個節點，即3，删除節點的next=null
public E remove(int index){
    Node<E> pre = dummyHead;
    for (int i = ; i < index; i++) {
        pre = pre.next;
    }
    if(pre == null)
        return null;
    Node<E> delNode = pre.next;
    pre.next = delNode.next;
    delNode.next = null;
    return delNode.e;
}

public E removeFirst(){
    return remove();
}

public E removeLast(){
    return remove(size - );
}

5）toString方法

@Override
public String toString(){

    StringBuilder sb = new StringBuilder();
    sb.append("LinkedList[ ");
    Node<E> current = dummyHead.next;
    //sb.append("NULL -> ");
    while (current !=  null){
        sb.append(current.e+" -> ");
        current = current.next;
    }
    sb.append("NULL]");
    return sb.toString();
}

2. 雙向連結清單

1）頭部插入資料

//添加一個對前一個節點的引用
public Node previous;

 /**
   * 插入一個結點，在頭結點後進行插入
   */
  public void insertFirst(long value){
      Node node = new Node(value);
      if(first == null){
          last = node;
      }else{
          first.previous = node;
      }
      node.next = first;
      first = node;
  }

2）尾部插入資料

/**
   * 插入一個結點，從尾結點進行插入
   */
  public void insertLast(long value){
      Node node = new Node(value);
      if (first == null){
          first = node;
      }else{
          last.next = node;
          node.previous = last;
      }
      last = node;
  }

3）頭部删除資料

/**
   * 删除一個結點，在頭結點後進行删除
   */
  public Node deleteFirst(){
     if(first == null). return;
      Node current = first;
      if(first.next == null){
          last = null;
      }else{
          first.next.previous = null;
      }
      first = first.next;
      return current;
  }

4）尾部删除資料

/**
   * 删除尾節點 從尾部進行删除
   */
  public Node deleteLast(){
      Node current = last;
      if(first.next == null){
          first = null;
      }else{
          last.previous.next = null;
      }
      //後一個節點用後一個節點的前一個節點替換
      last = last.previous;
      return last;
  }

5）删除節點資料

/**
  * 根據資料删除節點
  * @param value
  * @return
  */
 public Node delete(long value){

     Node current = first;
     if(current == null){
         return null;
     }
     while (current.data != value){
         current = current.next;
         if(current == null){
             return null;
         }
     }
     if(current == first){
         first = first.next;
     }else{
         //目前節點的前一個節點的下一個節點就是保留目前節點的引用
         current.previous.next = current.next;
     }
     return current;
 }

3. 用連結清單實作棧

基于實作的單連結清單LinkedList
public class LinkedListStack<E> implements Stack<E>{

    private LinkedList<E> linkedList;
    public LinkedListStack(){
        linkedList = new LinkedList<>();
    }

    //入棧
    @Override
    public void push(E e) {
        linkedList.addFirst(e);
    }

    //出棧
    @Override
    public E pop() {
        return linkedList.removeFirst();
    }

    //擷取棧頂元素
    @Override
    public E peek() {
        return linkedList.getFirst();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public int size() {
        return linkedList.size();
    }

    @Override
    public String toString(){

        StringBuilder sb = new StringBuilder();
        sb.append("LinkedList[ ");
        Node<E> current = linkedList.getNode();
        while (current !=  null){
            sb.append(current.e+" -> ");
            current = current.next;
        }
        sb.append("NULL ]");
        return sb.toString();
    }
}

4. 用連結清單實作隊列

1）構造函數

//隊頭 隊尾
private Node<E> front;
private Node<E> tail;
private int size;
public LinkedListQueue(){
    front = null;
    tail = null;
    size = ;
}

2）入隊

@Override
public void enqueue(E e) {
    //4->3->2->1
    Node<E> node = new Node<>(e);
    if(tail == null){
        tail = node;
        front = tail;
    }else{
        tail.next = node;
        tail = tail.next;
    }
    size++;
}

3）出隊

@Override
public E dequeue() {
    //4->3->2->1
    if(isEmpty())
        throw new IllegalArgumentException("隊列是空的，不能出隊");
    Node<E> current = front;
    front = front.next;
    current.next = null;
    if(front == null)
        tail = null;
    size--;
    return current.e;
}

4）toString方法

@Override
public String toString(){

    StringBuilder sb = new StringBuilder();
    sb.append("LinkedList size "+ size +"\n");
    Node<E> current = front;
    sb.append("front[ ");
    while (current !=  null){
        sb.append(current.e+" -> ");
        current = current.next;
    }
    sb.append("NULL ] tail");
    return sb.toString();
}

5.聯系方式

QQ:1509815887

資料結構之連結清單實作

分析：

1. 單向連結清單

2. 雙向連結清單

3. 用連結清單實作棧

4. 用連結清單實作隊列

5.聯系方式

繼續閱讀

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

基礎算法之二分查找

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

poj3249

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

PAT 1089 Insert or Merge[難]

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器