一、單鏈表

1、在我們數(shù)據(jù)結(jié)構(gòu)中，單鏈表非常重要。它里面的數(shù)據(jù)元素是以結(jié)點(diǎn)為單位，每個結(jié)點(diǎn)是由數(shù)據(jù)元素的數(shù)據(jù)和下一個結(jié)點(diǎn)的地址組成，在java集合框架里面  LinkedList、HashMap（數(shù)組加鏈表）等等的底層都是用鏈表實(shí)現(xiàn)的。

2、下面是單鏈表的幾個特點(diǎn)：

數(shù)據(jù)元素在內(nèi)存中存放的地址是不連續(xù)的：單鏈表的結(jié)點(diǎn)里面還定義一個結(jié)點(diǎn)，它里面保存著下一個結(jié)點(diǎn)的內(nèi)存地址，在實(shí)例化對象的時(shí)候，jvm會開辟不同內(nèi)存空間，并且是不連續(xù)的。

添加效率高：添加一個元素時(shí)，先找到插入位置的前一個，只需要將1，2個元素的連接斷開，將插入結(jié)點(diǎn)的next指向第一個元素的next

（1），然后將第一個元素的next指向插入結(jié)點(diǎn)（2），

不用在挪動后面元素。

刪除效率高：刪除一個元素時(shí)，先找到刪除位置，將前一個的next指向刪除位置的next，不用在挪動后面元素。

查詢效率低：查詢的時(shí)候必須從頭開始，依次遍歷，而數(shù)組因?yàn)樗膬?nèi)存是連續(xù)的，可以直接通過索引查找。

3、下面通過代碼來實(shí)現(xiàn)單鏈表結(jié)構(gòu)： 

package com.tlinkedList;  
/**  
* User:zhang  
* Date:2020/10/26  
**/  
public class TLinkedList<T> {  
  private Node head;//鏈表頭部  
  private int size;//鏈表元素的個數(shù)  
  public TLinkedList(){  
      head=null;  
      size=0;  
  }  
//    將結(jié)點(diǎn)作為內(nèi)部類。也可以新建一個Node類，作為結(jié)點(diǎn)  
  class Node{  
      private Node next;//下一個結(jié)點(diǎn)  
      private T t;//結(jié)點(diǎn)的數(shù)據(jù)  
      public Node(T t){  
          tthis.t=t;  
      }  
      public T getT() {  
          return t;  
      }  
      public void setT(T t) {  
          tthis.t = t;  
      }  
  }  
//    在鏈表頭部添加一個結(jié)點(diǎn)  
  public void addFirst(T t){  
      Node node = new Node(t);  
      node.next=head;  
      head=node;  
      size++;  
  }  
//    在鏈表中間添加一個結(jié)點(diǎn)  
  public void addMid(T t,int index){  
      Node node = new Node(t);  
      Node mid=head;  
      for (int i = 0; i < index - 1; i++) {  
          midmid=mid.next;  
      }  
      node.next=mid.next;  
      mid.next=node;  
      size++;  
  }  
//    在鏈表尾部添加一個結(jié)點(diǎn)  
  public void addLast(T t){  
      Node node = new Node(t);  
      Node last=head;  
      while (last.next!=null){  
          lastlast=last.next;  
      }  
      last.next=node;  
      node.next=null;  
      size++;  
  }  
//    刪除鏈表的頭結(jié)點(diǎn)  
  public void removeFirst(){  
      headhead=head.next;  
      size--;  
  }  
//    刪除鏈表的中間元素  
  public void removeMid(int index){  
      Node mid=head;  
      if (index==0){  
          removeFirst();  
          return;  
      }  
      int j=0;  
      Node qMid=head;  
      while (j<index){  
          qMid=mid;  
          midmid=mid.next;  
          j++;  
      }  
      qMid.next=mid.next;  
      size--;  
  }  
//    刪除鏈表的尾結(jié)點(diǎn)  
  public void removeLast(){  
      Node mid=head;  
      Node qMid=head;  
      while (mid.next!=null){  
           qMid=mid;  
           midmid=mid.next;  
      }  
      qMid.next= null;  
      size--;  
  }  
//    獲取鏈表指定下標(biāo)的結(jié)點(diǎn)  
  public Node get(int index){  
      Node mid=head;  
      if (index==0){  
          return head;  
      }  
      int j=0;  
      while (j<index){  
          midmid=mid.next;  
          j++;  
      }  
      return mid;  
  }  
  public static void main(String[] args) {  
      TLinkedList<String> linkedList = new TLinkedList<>();  
      linkedList.addFirst("hello1");  
      linkedList.addFirst("hello2");  
      linkedList.addFirst("hello3");  
      for (int i = 0; i < linkedList.size; i++) {  
          System.out.println(linkedList.get(i).getT());  
      }  
//        linkedList.removeLast();  
//        linkedList.removeFirst();  
//        linkedList.addLast("hello4");  
      linkedList.addMid("hello",2);  
      System.out.println("--------------");  
      for (int i = 0; i < linkedList.size; i++) { 
          System.out.println(linkedList.get(i).getT());  
      }  
  }  
} 

結(jié)果如下：

二、棧(Stack)

1、一提到棧我們腦海就會浮現(xiàn)四個字“先進(jìn)后出”，沒錯，它就是棧的最大特點(diǎn)。

2、棧的應(yīng)用場景也非常多，比如將字符串反轉(zhuǎn)、jvm里面的棧區(qū)等等。

3、棧里面的主要操作有：

•  push（入棧）：將一個數(shù)據(jù)元素從尾部插入
•  pop（出棧）：將一個數(shù)據(jù)元素從尾部刪除
•  peek（返回棧頂元素）：將棧頂元素的數(shù)據(jù)返回

相當(dāng)于只有一個開口就是尾部，只能從尾進(jìn)，從尾出。

4、下面通過鏈表結(jié)構(gòu)實(shí)現(xiàn)棧結(jié)構(gòu)： 

package com.tStack;  
/**  
* User:zhang  
* Date:2020/10/26  
**/  
public class Test_Stack<T> {  
  private Node head;//棧的頭結(jié)點(diǎn)  
  private int size;//棧的元素個數(shù)  
  class Node{  
      private Node next;//下一個結(jié)點(diǎn)  
      private T t;//結(jié)點(diǎn)的數(shù)據(jù)  
      public Node(T t){  
          tthis.t=t;  
      }  
      public T getT() {  
          return t; 
      }  
      public void setT(T t) {  
          tthis.t = t;  
      }  
  }  
  public Test_Stack() {  
      head=null;  
      size=0;  
  }  
  public static void main(String[] args) {  
      Test_Stack<String> TStack = new Test_Stack<>();  
      TStack.push("hello1");  
      TStack.push("hello2");  
      TStack.push("hello3");  
      for (int i = 0; i < 3; i++) {  
          System.out.println(TStack.pop());  
      }  
  }  
//    入棧  
  public void push(T t){  
      Node node = new Node(t);  
      if (size==0){  
          node.next=head;  
          head=node;  
          size++;  
          return;  
      }  
      if (size==1){  
          head.next=node;  
          node.next=null;  
          size++;  
          return;  
      }  
      Node lastNode=head;  
      while (lastNode.next!=null){  
           lastNodelastNode=lastNode.next;  
      }  
      lastNode.next=node;  
      node.next=null;  
      size++;  
  }  
//    出棧  
  public T pop(){  
      if (size==0){  
          System.out.println("棧內(nèi)無值");  
          return null;  
      }  
      if (size==1){  
          T t = head.getT();  
          head=null;  
          size--;  
          return t;  
      }  
      Node lastNode=head;  
      Node qNode=head;  
      while (lastNode.next!=null){  
          qNode=lastNode;  
          lastNodelastNode=lastNode.next;  
      }  
      T t = lastNode.getT();  
      qNode.next=null;  
      size--;  
      return t;  
  }  
//    獲取棧里面元素的個數(shù)  
  public int getSize(){  
      return size;  
  }  
//    返回棧頂元素  
  public T peek(){  
      if (size==0){  
          System.out.println("棧內(nèi)無值");  
          return null;  
      }  
      if (size==1){  
          return head.getT();  
      }  
      Node lastNode=head;  
      while (lastNode.next!=null){  
          lastNodelastNode=lastNode.next;  
      }  
      return lastNode.getT();  
  }  
} 

結(jié)果：

三、隊(duì)列(Queue)

1、隊(duì)列的特點(diǎn)也用“先進(jìn)先出”四個字來概括。就是先進(jìn)去的元素先輸出出來。

2、我們常見的消息隊(duì)列就是隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)的。

3、隊(duì)列的常見操作如下：

•  put（入隊(duì)）：將一個結(jié)點(diǎn)插入到尾部。
•  pop（出隊(duì)）：將頭結(jié)點(diǎn)的下一個結(jié)點(diǎn)作為頭，然后將原來的頭結(jié)點(diǎn)刪除。

4、通過鏈表結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列： 

package com.tQueue;  
/**  
 * User:zhang  
 * Date:2020/10/26  
 **/  
public class TQueue<T> {  
    private Node front;//頭結(jié)點(diǎn)  
    private Node tail;//尾結(jié)點(diǎn)  
    private int size;//隊(duì)列中元素的個數(shù)  
    class Node {  
        private Node next;//下一個結(jié)點(diǎn)  
        private T t;//結(jié)點(diǎn)的數(shù)據(jù)  
        public Node(T t) {  
            tthis.t = t; 
        }  
        public T getT() {  
            return t;  
        }  
        public void setT(T t) {  
            tthis.t = t;  
        }  
    }  
    public int getSize() {  
        return size;  
    }  
    public void setSize(int size) {  
        this.size = size;  
    }  
    public TQueue() {  
        front = tail = null;  
    }  
    //    入隊(duì)  
    public void put(T t) {  
        Node node = new Node(t);  
        if (size == 0) {  
            front = tail = node;  
            size++;  
            return; 
         }  
        Node lastNode = front;  
        while (lastNode.next != null) {  
            lastNodelastNode = lastNode.next;  
        }  
        lastNode.next = node;  
        tail = node;  
        size++;  
    }  
    //    出隊(duì)  
    public T pop() {  
        if (size == 0) {  
            System.out.println("隊(duì)列中無值");  
            return null;  
        }  
        T t = front.getT();  
        frontfront=front.next;  
        size--;  
        return t;  
    }   
    public static void main(String[] args) {  
        TQueue<String> tQueue = new TQueue<>();  
        tQueue.put("Hello1");  
        tQueue.put("Hello2");  
        tQueue.put("Hello3");  
        for (int i = 0; i < 3; i++) {  
            System.out.println(tQueue.pop());  
        }  
    }  
} 

結(jié)果：