點(diǎn)擊上方 好好學(xué)java ，選擇 星標(biāo) 公眾號(hào)
重磅資訊，干貨，第一時(shí)間送達(dá)

今日推薦：推薦 19 個(gè) github 超牛逼項(xiàng)目！
個(gè)人原創(chuàng)100W +訪問(wèn)量博客：點(diǎn)擊前往，查看更多

作者：遠(yuǎn)航

cnblogs.com/yang-guang-zhang/p/13884023.html

一、單鏈表

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

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

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

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

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

不用在挪動(dòng)后面元素。

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

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

3、下面通過(guò)代碼來(lái)實(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;//鏈表元素的個(gè)數(shù)
  public TLinkedList(){
      head=null;
      size=0;
  }
//    將結(jié)點(diǎn)作為內(nèi)部類。也可以新建一個(gè)Node類，作為結(jié)點(diǎn)
  class Node{
      private Node next;//下一個(gè)結(jié)點(diǎn)
      private T t;//結(jié)點(diǎn)的數(shù)據(jù)
      public Node(T t){
          this.t=t;
      }

      public T getT() {
          return t;
      }

      public void setT(T t) {
          this.t = t;
      }
  }
//    在鏈表頭部添加一個(gè)結(jié)點(diǎn)
  public void addFirst(T t){
      Node node = new Node(t);
      node.next=head;
      head=node;
      size++;
  }
//    在鏈表中間添加一個(gè)結(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++) {
          mid=mid.next;
      }
      node.next=mid.next;
      mid.next=node;
      size++;
  }
//    在鏈表尾部添加一個(gè)結(jié)點(diǎn)
  public void addLast(T t){
      Node node = new Node(t);
      Node last=head;
      while (last.next!=null){
          last=last.next;
      }
      last.next=node;
      node.next=null;
      size++;
  }
//    刪除鏈表的頭結(jié)點(diǎn)
  public void removeFirst(){
      head=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;
          mid=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;
           mid=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){
          mid=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、一提到棧我們腦海就會(huì)浮現(xiàn)四個(gè)字“先進(jìn)后出”，沒(méi)錯(cuò)，它就是棧的最大特點(diǎn)。

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

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

push（入棧）：將一個(gè)數(shù)據(jù)元素從尾部插入
pop（出棧）：將一個(gè)數(shù)據(jù)元素從尾部刪除
peek（返回棧頂元素）：將棧頂元素的數(shù)據(jù)返回
相當(dāng)于只有一個(gè)開(kāi)口就是尾部，只能從尾進(jìn)，從尾出。

4、下面通過(guò)鏈表結(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;//棧的元素個(gè)數(shù)
  class Node{
      private Node next;//下一個(gè)結(jié)點(diǎn)
      private T t;//結(jié)點(diǎn)的數(shù)據(jù)
      public Node(T t){
          this.t=t;
      }

      public T getT() {
          return t;
      }

      public void setT(T t) {
          this.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){
           lastNode=lastNode.next;
      }
      lastNode.next=node;
      node.next=null;
      size++;
  }
//    出棧
  public T pop(){
      if (size==0){
          System.out.println("棧內(nèi)無(wú)值");
          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;
          lastNode=lastNode.next;
      }
      T t = lastNode.getT();
      qNode.next=null;
      size--;
      return t;
  }
//    獲取棧里面元素的個(gè)數(shù)
  public int getSize(){
      return size;
  }
//    返回棧頂元素
  public T peek(){
      if (size==0){
          System.out.println("棧內(nèi)無(wú)值");
          return null;
      }
      if (size==1){
          return head.getT();
      }
      Node lastNode=head;
      while (lastNode.next!=null){
          lastNode=lastNode.next;
      }
      return lastNode.getT();
  }
}

結(jié)果：

三、隊(duì)列(Queue)

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

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

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

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

4、通過(guò)鏈表結(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ì)列中元素的個(gè)數(shù)
    class Node {
        private Node next;//下一個(gè)結(jié)點(diǎn)
        private T t;//結(jié)點(diǎn)的數(shù)據(jù)

        public Node(T t) {
            this.t = t;
        }

        public T getT() {
            return t;
        }

        public void setT(T t) {
            this.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) {
            lastNode = lastNode.next;
        }
        lastNode.next = node;
        tail = node;
        size++;
    }

    //    出隊(duì)
    public T pop() {
        if (size == 0) {
            System.out.println("隊(duì)列中無(wú)值");
            return null;
        }
        T t = front.getT();
        front=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é)果：

文章有不足之處，歡迎大家留言指正，謝謝大家啦！

推薦文章

基于SpringBoot的ERP系統(tǒng)，自帶進(jìn)銷存+財(cái)務(wù)+生產(chǎn)功能
2020年國(guó)內(nèi)互聯(lián)網(wǎng)公司的薪酬排名！
不要再封裝各種Util工具類了，這個(gè)神級(jí)框架值得擁有！
寫(xiě)博客能月入10K？
一款基于 Spring Boot 的現(xiàn)代化社區(qū)（論壇/問(wèn)答/社交網(wǎng)絡(luò)/博客）
更多項(xiàng)目源碼

這或許是最美的Vue+Element開(kāi)源后臺(tái)管理UI
推薦一款高顏值的 Spring Boot 快速開(kāi)發(fā)框架
一款基于 Spring Boot 的現(xiàn)代化社區(qū)（論壇/問(wèn)答/社交網(wǎng)絡(luò)/博客）
13K點(diǎn)贊都基于 Vue+Spring 前后端分離管理系統(tǒng)ELAdmin，大愛(ài)
想接私活時(shí)薪再翻一倍，建議根據(jù)這幾個(gè)開(kāi)源的SpringBoot項(xiàng)目

Java實(shí)現(xiàn)單鏈表、棧、隊(duì)列三種數(shù)據(jù)結(jié)構(gòu)

重磅資訊，干貨，第一時(shí)間送達(dá)

今日推薦：推薦 19 個(gè) github 超牛逼項(xiàng)目！

個(gè)人原創(chuàng)100W +訪問(wèn)量博客：點(diǎn)擊前往，查看更多

一、單鏈表

二、棧(Stack)

三、隊(duì)列(Queue)

推薦文章

Java實(shí)現(xiàn)單鏈表、棧、隊(duì)列三種數(shù)據(jù)結(jié)構(gòu)

重磅資訊，干貨，第一時(shí)間送達(dá)

今日推薦：推薦 19 個(gè) github 超牛逼項(xiàng)目！

個(gè)人原創(chuàng)100W +訪問(wèn)量博客：點(diǎn)擊前往，查看更多

二、棧(Stack)

三、隊(duì)列(Queue)