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

结果：

 

很赞哦!（3）