Java中的单链表、栈、队列三种数据结构

刺骨的言语ヽ痛彻心扉 2022-10-29 04:27 180阅读 0赞

# 一、单链表 #

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

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

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

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

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

不用在挪动后面元素。

![图片][1cdc6ffaf3ce2399aed2833445d57fd7.png]

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

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

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

package com.tlinkedList;
    
    /**
    * User:zhang
    * Date:2020/10/26
    **/
    public class TLinkedList<T> {
      private Node head;//链表头部
      private int size;//链表元素的个数
      public TLinkedList(){
          head=null;
          size=0;
      }
    //    将结点作为内部类。也可以新建一个Node类，作为结点
      class Node{
          private Node next;//下一个结点
          private T t;//结点的数据
          public Node(T t){
              this.t=t;
          }
    
          public T getT() {
              return t;
          }
    
          public void setT(T t) {
              this.t = t;
          }
      }
    //    在链表头部添加一个结点
      public void addFirst(T t){
          Node node = new Node(t);
          node.next=head;
          head=node;
          size++;
      }
    //    在链表中间添加一个结点
      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++;
      }
    //    在链表尾部添加一个结点
      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++;
      }
    //    删除链表的头结点
      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--;
      }
    //    删除链表的尾结点
      public void removeLast(){
          Node mid=head;
          Node qMid=head;
          while (mid.next!=null){
               qMid=mid;
               mid=mid.next;
          }
          qMid.next= null;
          size--;
      }
    //    获取链表指定下标的结点
      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());
          }
      }
    }

结果如下：  
![图片][6802f3a4fafb5a7ed7d2dffa4eb7e657.png]

# 二、栈(Stack) #

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

![图片][99ffadfe4831a54660b0fc6cfc853761.png]  
2、栈的应用场景也非常多，比如将字符串反转、jvm里面的栈区等等。

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

*  push（入栈）：将一个数据元素从尾部插入
 *  pop（出栈）：将一个数据元素从尾部删除
 *  peek（返回栈顶元素）：将栈顶元素的数据返回  
    相当于只有一个开口就是尾部，只能从尾进，从尾出。

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

package com.tStack;
    
    
    /**
    * User:zhang
    * Date:2020/10/26
    **/
    public class Test_Stack<T> {
      private Node head;//栈的头结点
      private int size;//栈的元素个数
      class Node{
          private Node next;//下一个结点
          private T t;//结点的数据
          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("栈内无值");
              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;
      }
    //    获取栈里面元素的个数
      public int getSize(){
          return size;
      }
    //    返回栈顶元素
      public T peek(){
          if (size==0){
              System.out.println("栈内无值");
              return null;
          }
          if (size==1){
              return head.getT();
          }
          Node lastNode=head;
          while (lastNode.next!=null){
              lastNode=lastNode.next;
          }
          return lastNode.getT();
      }
    }

结果：

![图片][6ca76703d11e69aa959f88900d7b726b.png]

# 三、队列(Queue) #

1、队列的特点也用“先进先出”四个字来概括。就是先进去的元素先输出出来。  
![图片][ffa416cd88df4ee462bfd61ab6226b2e.png]

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

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

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

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

package com.tQueue;
    
    /**
     * User:zhang
     * Date:2020/10/26
     **/
    public class TQueue<T> {
        private Node front;//头结点
        private Node tail;//尾结点
        private int size;//队列中元素的个数
        class Node {
            private Node next;//下一个结点
            private T t;//结点的数据
    
            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;
        }
    
        //    入队
        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++;
        }
    
        //    出队
        public T pop() {
            if (size == 0) {
                System.out.println("队列中无值");
                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());
            }
        }
    }

结果：  
![图片][15b43b2a2c1f96f9b21b68125d41739a.png]

[1cdc6ffaf3ce2399aed2833445d57fd7.png]: /images/20221024/606c247831ff4461a8de0357d2f5b0b2.png
[efc45dc46f2e230c844cf6e6d195b16d.png]: /images/20221024/90a7d953fc2b43b4b239dfa3ee499a57.png
[6802f3a4fafb5a7ed7d2dffa4eb7e657.png]: /images/20221024/79473de52124446db0d912fc56349e8a.png
[99ffadfe4831a54660b0fc6cfc853761.png]: /images/20221024/3180260dac7e4a98bc2a9afa5bef7ce4.png
[6ca76703d11e69aa959f88900d7b726b.png]: /images/20221024/03fbe953acea493bac95eb095723a5d1.png
[ffa416cd88df4ee462bfd61ab6226b2e.png]: /images/20221024/c5cbaae723a140e98193e81ef199aed9.png
[15b43b2a2c1f96f9b21b68125d41739a.png]: /images/20221024/65b6224d2f66434cad06dbf858f9d503.png