欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

数据结构 - 单链表和双链表（Java 实现）

最编程 2024-07-19 07:23:33
...

文章目录

  • 前言
    • 链表：
    • 链表分类：
  • 一 单链表
    • 单链表的实现：
    • 节点的实现
    • 头插法：
    • 尾插法
    • 在任意位置插入数据：
    • 查找单链表中是否有key关键字（即是否有值为key的数据）
    • 删除第一次出现的关键字为key的节点
    • 删除所有值为key的节点
    • 获取单链表的长度
    • 清空链表
    • 单链表的优缺点：
  • 二、双链表
    • 双向链表的实现：
    • 内部类实现节点
    • 头插法：
    • 尾插法：
    • 任意位置插入数据
    • 查找是否关键字key是否在双链表当中
    • 删除第一次出现关键字为key的节点
    • 删除所有值为key的节点
    • 得到链表的长度
    • 清空链表
  • java提供的LinkedList接口
    • 实现的接口：
    • 构造方法
    • 关于java提供的LinkedList方法的使用
      • 常用的方法有这几种：
      • 关于链表的遍历
    • 双向链表的优缺点
    • ArrayList和LinkedList对比

前言

链表：

链表是线性表的一种，在物理存储结构上不一定连续（绝大多数情况下非连续），在数据逻辑顺序上，将节点用指针链接起来实现连续。
链表是由一个一个的节点组成

在这里插入图片描述
节点：节点中分为数据域与指针域，数据域用于存放数据，指针域用于存放下一个节点的引用地址。
在这里插入图片描述

链表分类：

在这里插入图片描述
所谓带头是指链表中有一个固定的头结点，此头结点携带的数据无效（类似于火车的火车头不承载乘客一样。）
所谓单向是指：链表的头结点可以通过指针遍历到尾结点，但不能够从尾结点遍历到头结点。
如图：
在这里插入图片描述

相应的，双向链表则既可以从头遍历到尾结点，又可以从尾结点遍历到头结点。
如图：
在这里插入图片描述

所谓循环是指尾结点的指针指向头结点：
在这里插入图片描述

下面所学的单链表与双链表分别是不带头单向非循环链表与不带头双向非循环链表。

一 单链表

单链表的实现：

在java中实现一个单链表通过定义一个类来实现：

public class  MySingleList {


   public Node head;  //创建指向链表头结点的指针,注意此时的head节点与带头链表的头不同，此时head
   //指向节点的值是有效的

    //关于链表中的方法
    //头插法
    public void addFirst(int data);
    //尾插法
    public void addLast(int data);
    // 任意位置插入，第一个节点为0号下标
    public void addIndex(int index,int data);
    //判断指定数据关键字是否在单链表中
    public boolean contains(int key);
    //删除链表中第一次出现关键字key的节点
    public  void remove(int key);
    //删除所有值为key的节点
    public void removeAllkey(int key);
    //得到单链表的长度
    public int  size();
    //清空单链表
    public void clear();
    //展示单链表
    public void display();
}

节点的实现

节点是一个独立的对象，在java中也通过类来实现，节点是单链表的一部分，所以我们在链表类中定义一个内部类来实现节点。

static class Node
    {
        public   int data; //用于存放数据
        public Node next; //用于存放地址

        public Node(int data) {
            this.data = data;
        }
    }

头插法：

思路：将新创建节点的指针（next）指向头（head），再改头为当前节点。
即使head的值为null ，即链表为空，此代码也不会有问题。

  public void addFirst(int data) {
            Node cur = new Node(data);
            cur.next = head;
            head = cur;
        
    }

尾插法

思路：先判断链表是否为空（即head是否为null）,如果为空,，则使得头指针head指向新的节点
如果不为空，则找到尾结点，再将尾结点的next指针指向新建节点。

public void addLast(int data) {
        //尾插法：
      
        //头节点是否为空，
        if(head == null){
            head = new Node(data);
        }else {
            Node cur = head;
            //找到链表中最后一个节点
            while (cur.next!=null){
                cur = cur.next;
            }
            //找到最后一个节点后，进行尾插
            cur.next = new Node(data);
        }
    }

在任意位置插入数据：

  1. 先判断指定下标index是否合法。
  2. 如果index为0，则采取头插法，如果index为链表长度即链表末尾，则采取尾插法
  3. 如果是中间节点，保存插入位置的前一个节点地址，改动前一个节点的next与插入节点的next值
  public void addIndex(int index, int data) {
        //需要判断index的值是否合法。
        if(index>size()||index<0){
            System.out.println("index的值不合法");
            return;
        }
           if(index ==0) {
               //如果index处于顺序表的头节点处
               addFirst(data);
               return;
           }
            //如果index处于顺序表末尾的后一位
            if (index ==size()){
                //则直接调用addLast方法即可
                addLast(data);
                return ;
                }
            if(index>0&&index<size()){
                //进行中间插入，需要找到插入位置的前一个节点，找到插入位置
                Node cur = head;
                while(index>1){
                    cur = cur.next;
                    index--;
                }
                //此为插入位置的前一个节点
                Node prev = cur;
                //此为插入位置的节点
                cur = prev.next;
                //创建一个新的节点并插入：
                Node cur2 = new Node(data);
                cur2.next =cur;
                prev.next = cur2;
                return;
            }
        }

查找单链表中是否有key关键字（即是否有值为key的数据）

思路：直接遍历即可。

 public boolean contains(int key) {
        //判断链表中是否包含关键字
        Node cur = head;
        while (cur!= null){
            if (cur.data == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

删除第一次出现的关键字为key的节点

思路1：

  1. 先判断链表是否为空，空直接返回
  2. 链表不为空时，遍历链表，当出现关键字key时，判断是否为头结点，如果是则head指向头结点的下一个节点
  3. 如果关键字不是头结点的数据，则让前一个节点的下一个节点置为当前节点的下一个节点;

思路2：也可以将涉及头结点的算法整理到一边，即如果头结点为null与头结点的值为key的情况，然后再处理第一次出现的key为中间节点的情况，这样看起来代码更简洁。

思路1 ：

public void remove(int key) {
        if(head ==null){
            return;
        }
        //移除第一次出现的关键字key
        Node cur = head;
        Node prev = cur;
        while (cur!=null){
            if(cur.data ==key){
                //如果此时cur节点为头节点
             if(cur ==head){
                 head = head.next;
                 return;
             }else {
                 //如果此时cur节点是非头节点
                 prev.next = cur.next;
                 return;
             }
            }
            prev = prev.next;
            cur = cur.next;
        }
    }

思路2：

public void remove(int key){
        if(head == null){
            return;
        } else if (head .data == key) {
            head = head.next;
            return;
        }
        Node cur = head.next;
        Node prev = head;

        while(cur != null){
            if(cur.data == key){
                prev.next = cur.next;
                return;
            }
            prev = prev.next;
            cur = cur.next;
          
        }
    }

删除所有值为key的节点

思路：只采用一次遍历，便将所有指定的节点删除
与删除一个节点的算法思想2大致相同.

public void removeAllKey(int key){
        if(head == null){
            return;
        } //这里不需要再加head.data =key的情况，因为下方已经有了这个语句，
        Node cur = head.next;
        Node prev = head;

        while(cur != null){
            if(cur.data == key){
                prev.next = cur.next; //祛除了prev.next对cur节点的引用
                cur = cur.next;

            }else {
                cur = cur.next;
                prev = prev.next;
            }
        }
        if(head.data == key){
            head = head.next;
        }
    }

如果将头结点删除与中间节点，尾结点删除混合在一起，算法就会麻烦与复杂很多。

获取单链表的长度

  public int  size() {
       int count = 0;
       Node cur = head;
       while (cur!=null){
           count++;
           cur = cur.next;

       }
       return count;
    }

清空链表

思想1：通过遍历链表，将头结点的值不断后移，最终将链表置为空（头结点后移中，没有引用指向前面的节点，前面的节点自动被回收）
思想2：也可以不移动头，遍历链表，将每个节点的next指针置为null，最后将头指针置为null，这种方法麻烦一些

思想1：

public void clear(){
        Node cur = head;
        while (cur != null){
            head = cur.next;
            //不用将cur =null ，因为系统回收堆区的条件是没有引用引用这块空间。
            cur = head;
        }
    }

思想2：

public void clear() {
           //清空链表
        Node cur= head;
        while (cur!=null){
            Node curN = cur; //将当前节点赋给curN
            cur = cur.next;    //指针后移
            curN.next  = null; //将当前节点的next值置为空
        }
     //最后头结点再置为null
        head = null;
    }

单链表的优缺点：

优点：单向链表增加删除节点简单。
缺点：只能找到后继节点，不能找到前驱节点，只能从前往后遍历，不可以从后往前遍历。

二、双链表

在java集合类中使用的链表是无头双向非循环链表，使用的不是单链表。
在这里插入图片描述

双向链表的实现：

public class MyLinkedList {
    public ListNode head; //指向链表的首结点（此节点的数据是有效的）
    public ListNode last;//指向链表的尾结点
     //头插法
     public void addFirst(int data);
     //尾插法
     public void addLast(int data);
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data);
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key);
     //删除第一次出现关键字为key的节点
     public void remove(int key);
     //删除所有值为key的节点
     public void removeAllKey(int key);
     //得到链表的长度
     public int size();
     //情空链表
     public void clear();
 }

内部类实现节点

  static class ListNode{
         int data;
         ListNode next; //指向下一个节点
         ListNode prev;//指向前一个节点

        public ListNode(int data) {
            this.data = data;
        }
    }

头插法：

实现思想：

  1. 如果头结点为空，则将head与last指针指向新的节点
  2. 如果不为空则将新的节点的下一个节点置为头结点
  3. 头结点的前一个节点置为新节点, 然后将新节点的引用赋给head.
    public void addFirst(int data){
             //双向链表的头插
            //两种情况：1 头结点为空，2.头结点不为空、
             ListNode cur = new ListNode(data);
             if(head ==null){
                 last = head = cur;
             }else {
                 //如果头结点不为空
                 cur.next = head;
                 head.prev = cur;
                 head = cur;
             }
         }

尾插法：

实现思想：先判断链表是否为空，

  1. 如果为空，则直接将新节点的引用赋给head与last
  2. 如果不为空，则将last的下一个节点置为新节点，新节点的前一个节点置为last，最后由last引用新节点。
     public void addLast(int data){
             //先找到尾结点
            ListNode cur = new ListNode(data);
             if(head == null){
                 last = head = cur;
                 return;
             }
          //有了last指针，便不再需要遍历链表了
             //如果链表不为空：
             last.next = cur;
             cur.prev = last;
             last  = cur;
         }

任意位置插入数据

实现思路：

  1. 判断位置是否合法，不合法直接返回
  2. 插入位置为头节点，对应调用头插方法，是尾结点则采用尾插方法。
  3. 插入位置为中间节点，找到插入位置为对应节点，将插入节点前驱prev改为对应节点前驱，对应节点前驱改为插入节点，插入节点后继next改为对应节点。
    public void addIndex(int index,int data){
             //先判断index值是否合法
             if(index<0||index>size()){
                 System.out.println("index值不合法");
                 return;
             }

             if(index ==0){
                 addFirst(data);
                 return;
             }
             if(index ==size()){
                 addLast(data);
                 return ;
             }
             if(index>0&&index<size()){
                   //中间插入
                 ListNode cur = head;
                 while(index>0){
                     //先找到cur位置
                     cur =cur.next;
                     index--;
                 }
                 ListNode curN = new ListNode(data);
                 //将插入的节点与左右两边的节点相连
                 curN.next = cur;
                 curN.prev = cur.prev;
                 curN.prev.next = curN;
                 cur.prev = curN;

                    return ;
             }
         }

查找是否关键字key是否在双链表当中

实现思想：直接遍历即可

   public boolean contains(int key){
             //判断关键字key是否在双链表中
             ListNode cur = head;

             while (cur!=null){
                 if(cur.data == key){
                     return  true;
                 }
                 cur =cur.next;
             }
             return  false;
         }

删除第一次出现关键字为key的节点

实现思想：

  1. 首先遍历链表，判断第一个关键字key出现的位置
  2. 如果是头结点，则将下一个节点的prev指针置为null,然后head指针指向下一个节点
  3. 如果是其他节点，先执行前一个节点的next指针指向当前节点的下一个节点，然后判断此节点是否为尾结点，如果是，last指针指向的前一个节点，
  4. 不是则将下一个节点的prev指针指向当前节点的前一个节点
  public void remove(int key) {
            
             ListNode cur = head;
             while (cur != null) {
                 if (cur.data == key) {
                     //需要判断此节点是什么节点
                     if (cur == head) {
                         cur.next.prev = null;
                         head = head.next;
                         return;
                     } else {
                         cur.prev.next = cur.next;
                         if (cur == last) {
                             last = last.prev;
                             return;
                         } else {
                             cur.next.prev = cur.prev;
                             return;
                         }
                     }
                 }
                 cur = cur.next;
             }
         }

删除所有值为key的节点

实现思想：与删除一个节点的思路相同，不进行返回，使其循环即可

 public void removeAllKey(int key) {
              ListNode cur = head;

              while (cur != null) {
                  if (cur.data == key) {
                      //需要判断此节点是什么节点
                      if (cur == head) {
                          cur.next.prev = cur.prev;
                          head = head.next;
                      }else {
                          cur.prev.next = cur.next;
                          if(cur ==last){
                              last =last.prev;
                          }else {
                              cur.next.prev = cur.prev;
                          }
                      }
                  }
                  cur =cur .next;
              }
          }

得到链表的长度

思想：直接遍历

     public int size(){
             ListNode cur = head;
             int count = 0;
             while (cur !=null){
                 count++;
                 cur = cur.next;
             }
             return count;
         }

清空链表

实现思想：先将每一个节点的prev指针与next指针置为null,最后清空head与last指针

             ListNode cur = head;
             while(cur !=null){
                 ListNode curN = cur.next;
                 cur.prev = null;  //是将当前节点中的两个指针域置为空，此时cur.prev是本指针置为空，而不是cur.prev指向的节点为空
                                          //要用辩证思维看待，而不是形式逻辑
                 cur.next = null;
																				

						

							上一篇：							
								Arcane - 第 1 章 应急响应 - Linux 入侵故障排除 - 摘要							
						

						

							下一篇：							
								Elasticsearch：将 Logstash 日志保存到 Elasticsearch							
						

					

															

						

							推荐阅读