服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|编程技术|正则表达式|C/C++|

服务器之家 - 编程语言 - JAVA教程 - Java实现单链表、栈、队列三种数据结构

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

2020-10-28 21:23Java知音 JAVA教程

本文介绍了单链表、栈、队列三种数据结构。一起来看看吧。

一、单链表

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

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

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

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

(1),然后将第一个元素的next指向插入结点(2),

不用在挪动后面元素。

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

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

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

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

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.nextnull 

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

      }  

  }  

结果如下:

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

二、(Stack)

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

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

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

  }  

结果:

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

三、队列(Queue)

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

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

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

        }  

    }  

结果:

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

延伸 · 阅读

精彩推荐