数据结构（二）之链表详解

客官°小女子只卖身不卖艺 2023-09-27 13:29 108阅读 0赞

**目录**

一、链表的定义

二、链表的种类

三、不带头单向非循环链表实现

四、不带头双向非循环链表实现

五、链表的优缺点

--------------------

在上一篇文章里详细介绍了顺序表的定义与用法，这篇文章则重点介绍链表的详细用法与优缺点

## 一、链表的定义 ##

链表又叫做线性表的链式存储，由一个个的节点（或者结点）组成，类似生活中的火车车厢一节节的串在一起。链表是一种**物理存储结构上非连续**存储结构，数据元素的**逻辑顺序**是通过链表中的**引用链接**次序实现的 。

![d80072d06cd145e4986cee33bb61c64d.png][]![4231c1e4fa734fb4a04d4507ea576397.png][]

**链表中的每一个结点包含两部分：一个叫数据域：存储数据元素信息，另外一个叫指针域：存储下一个节点的存储地址。**

![6ae15f218e7f42b38784e0b88c81d90f.png][]

![52cc86a1b28f48949b25976a21fc5bfa.png][]

对于线性表来说，总得有个头有个尾，链表也不例外。**我们把链表的第一个节点前设一个节点，称为头节点。头节点的数据域可以不存储任何信息，头节点的指针域存储指向第一个节点的指针。**线性链表的最后一个节点的指针域为空（用NULL表示）

带头单向非循环链表示例图：

![0c6f0fa23be14719972aac5e9f6dca99.png][]

## 二、链表的种类 ##

链表根据是否带有头节点，不带头节点，单向或者双向，循环或者非循环可以组合成8种情况：

带头 双向 循环链表 不带头 双向 循环链表

带头 双向 非循环链表 不带头 双向 非循环链表

带头 单向 循环链表 不带头 单向 循环链表

带头 单向 非循环链表 不带头 单向 非循环链表

其中 双向值得是带有2个指针域，一个指针域指向下一节点的存储地址，另一个指针域指向上一节点的存储地址。

![c919f322e94747dca94ca4751e202203.png][]

虽然有这么多的链表的结构，我们重点掌握两种:**不带头单向非循环链表**和**不带头双向非循环链表**

##  ##

## 三、不带头单向非循环链表实现 ##

（1）创建链表

public class ListNode{
      public int val;  //创建数据域
      public ListNode next; //创建指针域，//存储下一个节点的地址
      public ListNode head;//代表单链表的头结点的引用
      public ListNode(){
         this.val = val;
         }
      public void createListNode(）{ //创建一个链表
           ListNode listnode1 = new ListNode(12);//12为第一节点的val值
           ListNode listnode2 = new ListNode(15);
           ListNode listnode3 = new ListNode(23);
           ListNode listnode4 = new ListNode(44);
           
            listnode1.next =  listnode2;
            listnode2.next = listnode3;
            listnode3.next = listnode4;
          
            this.head = listnode1;
       }
    }

（2）遍历打印链表元素

public void display() {
       ListNode cur = head; 
       while(cur!=null){ 
           System.out.print(cur.val+" ");
           cur=cur.next;
      }
        System.out.println();
    }

(3)头插法

public void addFrist(int data){
          ListNode node = new ListNode(data);//创建一个新的节点进行头插  
         
          node.next=this.head;
          this.head=node;
    }

(4)尾插法

public void addLast(int data){
       ListNode node = new ListNode (data);
        if(this.head==null){
             this.head = node;
    }else{
             ListNode cur = head;
             while(cur.next!=null){//找到最后一个节点，因为最后一个节点的next为null
                  cur=cur.next;
       }
            cur.next=node;
     }
    
    }

(5) 任意位置插入，第一个数据节点为0号下标

public void addIndex(int index,int data){
        ListNode node =new ListNode(data);   
       if(index < 0 || index > size() ){
            System.out.println("插入位置不合法")；
                return;
        }
        if(index ==0){//头插
            addFirst(data);
             return;    
     }
          if(index == size()){//尾插
            addLast(data);
             return;    
     }
          while(index-1 !=0){ //找到下标index的前一个位置即index-1
             ListNode cur = head;
             cur=cur.next; //当循环结束时，此时cur指向index-1的节点
             index--;
      }
            node.next=cur.next; //先绑定后面节点
            cur.next=node;
    }

（6）查找是否包含关键字key是否在单链表当中

public boolean contains(int data){
       ListNode cur = head;
       while(cur != null){
         if(cur.val == key){
              return true; 
       } 
          cur=cur.next;
     }
             return false;
    }

(7)删除所有值为key的节点

public void removeAll(int key){
      ListNode cur = head;
      if(head == null){
           return null;
        }
       while(head !=null && head.val == key){ //先判断头节点的val是否等于data
               head = head.next;
      }
       while(cur != null){
          while(cur.next != null && cur.next.val == key){ //此时已确认了头节点不等于data，从第二节点开始循环判断
                    cur.next=cur.next.next;
        }
                cur=cur.next;
      }
    }

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

public void remove (int key){
       if(head == null){
           return null;
      }
       if( head.val == key){
               head = head.next;
               return;
     }
         ListNode cur = head;
        while( cur.next!=null){ //找到key的前一个节点
          if( cur.next.val == key){
                    return;
       }
               cur=cur.next;
      }
               cur.next=cur.next.next; //删除key所在节点
     }

（9）获取单链表的长度

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

## 四、**不带头双向非循环链表实现** ##

public class MyLinkedList {
    //头插法
    public void addFirst(int data){ }
    //尾插法
    public void addLast(int data){}
    //任意位置插入,第一个数据节点为0号下标
    public void 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(){}
    }

##  ##

## 五、链表的优缺点 ##

优点：

1、对于频繁插入和删除数据的操作，链表的效率很高

2、单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

缺点：

1、在查找数据元素上，时间复杂度为O(N)

2、链表不是一种随机存储结构，不能随机存取元素。

[d80072d06cd145e4986cee33bb61c64d.png]: https://img-blog.csdnimg.cn/d80072d06cd145e4986cee33bb61c64d.png
[4231c1e4fa734fb4a04d4507ea576397.png]: https://img-blog.csdnimg.cn/4231c1e4fa734fb4a04d4507ea576397.png
[6ae15f218e7f42b38784e0b88c81d90f.png]: https://img-blog.csdnimg.cn/6ae15f218e7f42b38784e0b88c81d90f.png
[52cc86a1b28f48949b25976a21fc5bfa.png]: https://img-blog.csdnimg.cn/52cc86a1b28f48949b25976a21fc5bfa.png
[0c6f0fa23be14719972aac5e9f6dca99.png]: https://img-blog.csdnimg.cn/0c6f0fa23be14719972aac5e9f6dca99.png
[c919f322e94747dca94ca4751e202203.png]: https://img-blog.csdnimg.cn/c919f322e94747dca94ca4751e202203.png