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

共 1248字,需浏览 3分钟

 ·

2020-12-17 17:57

一、单链表


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){
          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          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          mid=mid.next;
          j++;
      }
      return mid;
  }
  public static void main(String[] args) {
      TLinkedList 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){
          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 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();
  }
}

结果:


三、队列(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) {
            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 tQueue = new TQueue<>();
        tQueue.put("Hello1");
        tQueue.put("Hello2");
        tQueue.put("Hello3");
        for (int i = 0; i < 3; i++) {
            System.out.println(tQueue.pop());
        }
    }
}

结果:



文章有不足之处,欢迎大家留言指正,谢谢大家啦!

源:cnblogs.com/yang-guang-zhang/p/13884023.html

版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢!





感谢阅读



浏览 23
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报