Java实现单链表、栈、队列三种数据结构

一、单链表

创新互联建站于2013年成立，是专业互联网技术服务公司，拥有项目成都做网站、网站建设、外贸营销网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元秦安做网站,已为上家服务,为秦安各地企业和个人服务,联系电话:18982081108

1、在我们数据结构中，单链表非常重要。它里面的数据元素是以结点为单位，每个结点是由数据元素的数据和下一个结点的地址组成，在java集合框架里面  LinkedList、HashMap（数组加链表）等等的底层都是用链表实现的。

2、下面是单链表的几个特点：

数据元素在内存中存放的地址是不连续的：单链表的结点里面还定义一个结点，它里面保存着下一个结点的内存地址，在实例化对象的时候，jvm会开辟不同内存空间，并且是不连续的。

添加效率高：添加一个元素时，先找到插入位置的前一个，只需要将1，2个元素的连接断开，将插入结点的next指向第一个元素的next

（1），然后将第一个元素的next指向插入结点（2），

不用在挪动后面元素。

删除效率高：删除一个元素时，先找到删除位置，将前一个的next指向删除位置的next，不用在挪动后面元素。

查询效率低：查询的时候必须从头开始，依次遍历，而数组因为它的内存是连续的，可以直接通过索引查找。

3、下面通过代码来实现单链表结构：

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

结果如下：

二、栈(Stack)

1、一提到栈我们脑海就会浮现四个字“先进后出”，没错，它就是栈的最大特点。

2、栈的应用场景也非常多，比如将字符串反转、jvm里面的栈区等等。

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

  •  push（入栈）：将一个数据元素从尾部插入
  •  pop（出栈）：将一个数据元素从尾部删除
  •  peek（返回栈顶元素）：将栈顶元素的数据返回

相当于只有一个开口就是尾部，只能从尾进，从尾出。

4、下面通过链表结构实现栈结构：

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

结果：

三、队列(Queue)

1、队列的特点也用“先进先出”四个字来概括。就是先进去的元素先输出出来。

2、我们常见的消息队列就是队列结构实现的。

3、队列的常见操作如下：

  •  put（入队）：将一个结点插入到尾部。
  •  pop（出队）：将头结点的下一个结点作为头，然后将原来的头结点删除。

4、通过链表结构实现队列：

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

结果：

分享标题：Java实现单链表、栈、队列三种数据结构
分享URL：http://www.csdahua.cn/qtweb/news35/508435.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 快上网

成都快上网为您推荐相关内容

品牌网站制作知识

同城分类信息

成都广告公司　　 　seo推广公司　　 　成都工商服务　　 　四川国泰民安消防　　 　凯亚自动化控制　　 　背发光字　　 　腾讯云香港空间　　 　整合营销　　 　高端网站设计　　 　重庆企业网站建设　　 　成都网络公司　　 　域名注册　　 　云服务器　　 　成都发电机维修保养公司　　 　h5响应式网站　　 　德阳电信机房　　 　成都添翼二手车　　 　成都多线服务器托管　　 　营山母婴护理　　 　成都响应式网站建设公司