自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

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

作者：佚名
開發(fā) 后端
本文介紹了單鏈表、棧、隊(duì)列三種數(shù)據(jù)結(jié)構(gòu)。一起來看看吧。

一、單鏈表

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é)點(diǎn)里面還定義一個(gè)結(jié)點(diǎn)，它里面保存著下一個(gè)結(jié)點(diǎn)的內(nèi)存地址，在實(shí)例化對象的時(shí)候，jvm會開辟不同內(nèi)存空間，并且是不連續(xù)的。

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

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

不用在挪動后面元素。

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

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

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

  1. package com.tlinkedList;  
  2. /**  
  3. * User:zhang  
  4. * Date:2020/10/26  
  5. **/  
  6. public class TLinkedList<T> {  
  7.   private Node head;//鏈表頭部  
  8.   private int size;//鏈表元素的個(gè)數(shù)  
  9.   public TLinkedList(){  
  10.       head=null;  
  11.       size=0;  
  12.   }  
  13. //    將結(jié)點(diǎn)作為內(nèi)部類。也可以新建一個(gè)Node類，作為結(jié)點(diǎn)  
  14.   class Node{  
  15.       private Node next;//下一個(gè)結(jié)點(diǎn)  
  16.       private T t;//結(jié)點(diǎn)的數(shù)據(jù)  
  17.       public Node(T t){  
  18.           tthis.t=t;  
  19.       }  
  20.       public T getT() {  
  21.           return t;  
  22.       }  
  23.       public void setT(T t) {  
  24.           tthis.t = t;  
  25.       }  
  26.   }  
  27. //    在鏈表頭部添加一個(gè)結(jié)點(diǎn)  
  28.   public void addFirst(T t){  
  29.       Node node = new Node(t);  
  30.       node.next=head;  
  31.       head=node;  
  32.       size++;  
  33.   }  
  34. //    在鏈表中間添加一個(gè)結(jié)點(diǎn)  
  35.   public void addMid(T t,int index){  
  36.       Node node = new Node(t);  
  37.       Node mid=head;  
  38.       for (int i = 0; i < index - 1; i++) {  
  39.           midmid=mid.next;  
  40.       }  
  41.       node.next=mid.next;  
  42.       mid.next=node;  
  43.       size++;  
  44.   }  
  45. //    在鏈表尾部添加一個(gè)結(jié)點(diǎn)  
  46.   public void addLast(T t){  
  47.       Node node = new Node(t);  
  48.       Node last=head;  
  49.       while (last.next!=null){  
  50.           lastlast=last.next;  
  51.       }  
  52.       last.next=node;  
  53.       node.next=null;  
  54.       size++;  
  55.   }  
  56. //    刪除鏈表的頭結(jié)點(diǎn)  
  57.   public void removeFirst(){  
  58.       headhead=head.next;  
  59.       size--;  
  60.   }  
  61. //    刪除鏈表的中間元素  
  62.   public void removeMid(int index){  
  63.       Node mid=head;  
  64.       if (index==0){  
  65.           removeFirst();  
  66.           return;  
  67.       }  
  68.       int j=0;  
  69.       Node qMid=head;  
  70.       while (j<index){  
  71.           qMid=mid;  
  72.           midmid=mid.next;  
  73.           j++;  
  74.       }  
  75.       qMid.next=mid.next;  
  76.       size--;  
  77.   }  
  78. //    刪除鏈表的尾結(jié)點(diǎn)  
  79.   public void removeLast(){  
  80.       Node mid=head;  
  81.       Node qMid=head;  
  82.       while (mid.next!=null){  
  83.            qMid=mid;  
  84.            midmid=mid.next;  
  85.       }  
  86.       qMid.next= null;  
  87.       size--;  
  88.   }  
  89. //    獲取鏈表指定下標(biāo)的結(jié)點(diǎn)  
  90.   public Node get(int index){  
  91.       Node mid=head;  
  92.       if (index==0){  
  93.           return head;  
  94.       }  
  95.       int j=0;  
  96.       while (j<index){  
  97.           midmid=mid.next;  
  98.           j++;  
  99.       }  
  100.       return mid;  
  101.   }  
  102.   public static void main(String[] args) {  
  103.       TLinkedList<String> linkedList = new TLinkedList<>();  
  104.       linkedList.addFirst("hello1");  
  105.       linkedList.addFirst("hello2");  
  106.       linkedList.addFirst("hello3");  
  107.       for (int i = 0; i < linkedList.size; i++) {  
  108.           System.out.println(linkedList.get(i).getT());  
  109.       }  
  110. //        linkedList.removeLast();  
  111. //        linkedList.removeFirst();  
  112. //        linkedList.addLast("hello4");  
  113.       linkedList.addMid("hello",2);  
  114.       System.out.println("--------------");  
  115.       for (int i = 0; i < linkedList.size; i++) { 
  116.           System.out.println(linkedList.get(i).getT());  
  117.       }  
  118.   }  
  119. } 

結(jié)果如下：

二、棧(Stack)

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

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

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

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

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

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

  1. package com.tStack;  
  2. /**  
  3. * User:zhang  
  4. * Date:2020/10/26  
  5. **/  
  6. public class Test_Stack<T> {  
  7.   private Node head;//棧的頭結(jié)點(diǎn)  
  8.   private int size;//棧的元素個(gè)數(shù)  
  9.   class Node{  
  10.       private Node next;//下一個(gè)結(jié)點(diǎn)  
  11.       private T t;//結(jié)點(diǎn)的數(shù)據(jù)  
  12.       public Node(T t){  
  13.           tthis.t=t;  
  14.       }  
  15.       public T getT() {  
  16.           return t; 
  17.       }  
  18.       public void setT(T t) {  
  19.           tthis.t = t;  
  20.       }  
  21.   }  
  22.   public Test_Stack() {  
  23.       head=null;  
  24.       size=0;  
  25.   }  
  26.   public static void main(String[] args) {  
  27.       Test_Stack<String> TStack = new Test_Stack<>();  
  28.       TStack.push("hello1");  
  29.       TStack.push("hello2");  
  30.       TStack.push("hello3");  
  31.       for (int i = 0; i < 3; i++) {  
  32.           System.out.println(TStack.pop());  
  33.       }  
  34.   }  
  35. //    入棧  
  36.   public void push(T t){  
  37.       Node node = new Node(t);  
  38.       if (size==0){  
  39.           node.next=head;  
  40.           head=node;  
  41.           size++;  
  42.           return;  
  43.       }  
  44.       if (size==1){  
  45.           head.next=node;  
  46.           node.next=null;  
  47.           size++;  
  48.           return;  
  49.       }  
  50.       Node lastNode=head;  
  51.       while (lastNode.next!=null){  
  52.            lastNodelastNode=lastNode.next;  
  53.       }  
  54.       lastNode.next=node;  
  55.       node.next=null;  
  56.       size++;  
  57.   }  
  58. //    出棧  
  59.   public T pop(){  
  60.       if (size==0){  
  61.           System.out.println("棧內(nèi)無值");  
  62.           return null;  
  63.       }  
  64.       if (size==1){  
  65.           T t = head.getT();  
  66.           head=null;  
  67.           size--;  
  68.           return t;  
  69.       }  
  70.       Node lastNode=head;  
  71.       Node qNode=head;  
  72.       while (lastNode.next!=null){  
  73.           qNode=lastNode;  
  74.           lastNodelastNode=lastNode.next;  
  75.       }  
  76.       T t = lastNode.getT();  
  77.       qNode.next=null;  
  78.       size--;  
  79.       return t;  
  80.   }  
  81. //    獲取棧里面元素的個(gè)數(shù)  
  82.   public int getSize(){  
  83.       return size;  
  84.   }  
  85. //    返回棧頂元素  
  86.   public T peek(){  
  87.       if (size==0){  
  88.           System.out.println("棧內(nèi)無值");  
  89.           return null;  
  90.       }  
  91.       if (size==1){  
  92.           return head.getT();  
  93.       }  
  94.       Node lastNode=head;  
  95.       while (lastNode.next!=null){  
  96.           lastNodelastNode=lastNode.next;  
  97.       }  
  98.       return lastNode.getT();  
  99.   }  
  100. } 

結(jié)果：

三、隊(duì)列(Queue)

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

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

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

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

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

  1. package com.tQueue;  
  2. /**  
  3.  * User:zhang  
  4.  * Date:2020/10/26  
  5.  **/  
  6. public class TQueue<T> {  
  7.     private Node front;//頭結(jié)點(diǎn)  
  8.     private Node tail;//尾結(jié)點(diǎn)  
  9.     private int size;//隊(duì)列中元素的個(gè)數(shù)  
  10.     class Node {  
  11.         private Node next;//下一個(gè)結(jié)點(diǎn)  
  12.         private T t;//結(jié)點(diǎn)的數(shù)據(jù)  
  13.         public Node(T t) {  
  14.             tthis.t = t; 
  15.         }  
  16.         public T getT() {  
  17.             return t;  
  18.         }  
  19.         public void setT(T t) {  
  20.             tthis.t = t;  
  21.         }  
  22.     }  
  23.     public int getSize() {  
  24.         return size;  
  25.     }  
  26.     public void setSize(int size) {  
  27.         this.size = size;  
  28.     }  
  29.     public TQueue() {  
  30.         front = tail = null;  
  31.     }  
  32.     //    入隊(duì)  
  33.     public void put(T t) {  
  34.         Node node = new Node(t);  
  35.         if (size == 0) {  
  36.             front = tail = node;  
  37.             size++;  
  38.             return; 
  39.          }  
  40.         Node lastNode = front;  
  41.         while (lastNode.next != null) {  
  42.             lastNodelastNode = lastNode.next;  
  43.         }  
  44.         lastNode.next = node;  
  45.         tail = node;  
  46.         size++;  
  47.     }  
  48.     //    出隊(duì)  
  49.     public T pop() {  
  50.         if (size == 0) {  
  51.             System.out.println("隊(duì)列中無值");  
  52.             return null;  
  53.         }  
  54.         T t = front.getT();  
  55.         frontfront=front.next;  
  56.         size--;  
  57.         return t;  
  58.     }   
  59.     public static void main(String[] args) {  
  60.         TQueue<String> tQueue = new TQueue<>();  
  61.         tQueue.put("Hello1");  
  62.         tQueue.put("Hello2");  
  63.         tQueue.put("Hello3");  
  64.         for (int i = 0; i < 3; i++) {  
  65.             System.out.println(tQueue.pop());  
  66.         }  
  67.     }  
  68. } 

結(jié)果：

 

 

責(zé)任編輯：龐桂玉 來源： Java知音
Java單鏈表數(shù)據(jù)結(jié)構(gòu)
相關(guān)推薦

2023-03-06 08:40:43

RedisListJava

2021-07-13 07:52:03

Python數(shù)據(jù)結(jié)構(gòu)

2012-05-16 17:05:33

Java數(shù)據(jù)結(jié)構(gòu)

2023-04-11 08:00:56

Redis類型編碼

2020-12-17 10:12:33

數(shù)據(jù)結(jié)構(gòu)算法隊(duì)列

2012-02-02 10:21:05

單鏈表nexthead

2021-03-10 08:42:19

Java數(shù)據(jù)結(jié)構(gòu)算法

2020-12-28 10:35:38

前端數(shù)據(jù)技術(shù)

2020-03-27 14:29:30

數(shù)據(jù)結(jié)構(gòu)棧堆

2025-01-13 06:10:00

2019-10-29 08:59:16

Redis底層數(shù)據(jù)

2021-08-03 10:24:59

數(shù)據(jù)跳躍鏈表結(jié)構(gòu)

2010-09-26 16:31:13

隨機(jī)查詢語句

2011-04-11 11:23:17

棧隊(duì)列數(shù)據(jù)結(jié)構(gòu)

2023-09-06 13:16:00

數(shù)據(jù)庫數(shù)據(jù)

2021-05-12 14:09:35

鏈表數(shù)據(jù)結(jié)構(gòu)線性結(jié)構(gòu)

2021-03-01 23:31:48

隊(duì)列實(shí)現(xiàn)棧存儲

2023-09-25 12:23:18

棧Python

2021-03-29 08:01:20

JavaScript數(shù)據(jù)結(jié)構(gòu)

2020-11-06 12:48:16

數(shù)據(jù)結(jié)構(gòu)算法分析
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號