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

一、单链表

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

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

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

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

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

不用在挪动后面元素。

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

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

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){  


          tthis.t=t;  


      }  


      public T getT() {  


          return t;  


      }  


      public void setT(T t) {  


          tthis.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++) {  


          midmid=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){  


          lastlast=last.next;  


      }  


      last.next=node;  


      node.next=null;  


      size++;  


  }  


//    删除链表的头结点  


  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--;  


  }  


//    删除链表的尾结点  


  public void removeLast(){  


      Node mid=head;  


      Node qMid=head;  


      while (mid.next!=null){  


           qMid=mid;  


           midmid=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){  


          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());  


      }  


  }  

} 

结果如下：

二、栈(Stack)

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

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){  


          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("栈内无值");  


          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;  


  }  


//    获取栈里面元素的个数  


  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){  


          lastNodelastNode=lastNode.next;  


      }  


      return lastNode.getT();  


  }  

} 

结果：

三、队列(Queue)

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

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) {  

            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;  


    }  


    //    入队  


    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++;  


    }  


    //    出队  


    public T pop() {  


        if (size == 0) {  


            System.out.println("队列中无值");  


            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());  


        }  


    }  

}