实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)

简介: 实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)



一.介绍单链表

1.链表及单链表

(1)什么是链表

链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

例如下面的这种数据结构,由一个个的结点组成。每个结点中存储着数据,又存储着其他结点的地址。

(2)什么是单链表

链表有三个特点:单向和双向、带头和不带头、循环和不循环;三三组合起来,一共8种情况(比如单向不带头不循环链表,就是本节的单向链表)。

单向和双向:单向表示每个结点只存后一个结点的地址;双向表示每个结点存放前后结点的地址。

区别:双向链表可以知道某个结点的前面结点,单向链表只能找到它后面的结点

带头和不带头:带头的链表会有一个固定的头结点(也称为哨兵位),所有操作都在头结点后面操作;不带头的链表则会自己定义一个结点用来表示当前链表的头,该结点也称为头结点,但是该头结点的位置是不停的变化的

区别:带头的链表,头结点的位置是固定不变的

循环和非循环:循环的链表,最后一个结点存放第一个结点的地址,非循环的链表最后一个结点存放的地址为null,也就是不指向任何的结点

区别:循环的链表也可以称为环,链表的遍历不会结束,而非循环会结束

本节介绍的单链表为:单向不带头非循环的链表,如下图的链表

2.定义一个链表

(1)定义一个链表(单独一个类)

public class MyList{
  
}

(2)将链表的功能包装称接口

public interface IList {
    public void addFirst(int data);//头插
    public void addLast(int data);//尾插
    public void add(int index,int data);//任意位置插入
    public boolean contains(int key);//检查key元素是否存在
    public void remove(int key);//删除第一个key
    public void removeAll(int key);//删除所有key
    public int size();//求链表的长度
    public void clear();//清空链表
    public void show();//打印链表
}

(3)链表实现该接口并重写方法

public class MyList implements IList{
  
    @Override
    public void addFirst(int data) {
        //头插
    }
    @Override
    public void addLast(int data) {
        //尾插    
    }
    @Override
    public void add(int index, int data) {
        //指定位置插入
    }
    @Override
    public boolean contains(int key) {
        //查找key元素
    }
    @Override
    public void remove(int key) {
        //删除第一个key     
    }
    @Override
    public void removeAll(int key) {
        //删除所有key结点
     
    }
    @Override
    public int size() {
        //求链表大小
    
    }
    @Override
    public void clear() {
        //清空链表
    }
    @Override
    public void show() {
       
    }
}

(4)定义链表的结点

我们将结点定义成一个内部类:包括数据域(data)和next域(存放下一个结点的地址)

public class MyList implements IList{
    class ListNode {
        public int data;//数据域
        public ListNode next;
        public ListNode(int data) {
            this.data = data;
        }
     }
    public ListNode head;//定位头的位置
  
    @Override
    public void addFirst(int data) {
        //头插
    }
    @Override
    public void addLast(int data) {
        //尾插    
    }
    @Override
    public void add(int index, int data) {
        //指定位置插入
    }
    @Override
    public boolean contains(int key) {
        //查找key元素
    }
    @Override
    public void remove(int key) {
        //删除第一个key     
    }
    @Override
    public void removeAll(int key) {
        //删除所有key结点
     
    }
    @Override
    public int size() {
        //求链表大小
    
    }
    @Override
    public void clear() {
        //清空链表
    }
    @Override
    public void show() {
       
    }
}

这样一个链表的基本结构就定义完成,接下来就是实现链表的一些功能即可

二.实现单链表的功能

链表的功能大概有以下几种,插入数据(头插,尾插,随机插入),打印链表的数据,删除链表的数据,查找某个元素和监测链表的大小。

接下来我们慢慢了解

1.插入数据

(1)头插法

下面的是头插法的代码

public void addFirst(int data) {
        //头插
        ListNode node = new ListNode(data);
        node.next = head;//
        head = node;
}

第一步:需要创造一个新的结点出来

第二步:连接链表;分为两种情况:第一种是空链表的时候(一个结点都没有的时候),另一种是非空链表的时候。以上的代码都满足

(2)尾插法

尾插法的逻辑稍微复杂一点点,同样需要考虑链表的两种情况;空链表时需要单独讨论,而当链表非空时,则需要找链表的尾巴。

第一步:创造新的结点

ListNode node = new ListNode(data);

第二步:考虑空链表的情况

if(head == null) {
      head = node;
      return;
}

第三步:找链表的尾巴

这个注意,我们不能移动head,head需要保持不动,不然链表的头将不见。

ListNode cur = head;
while(cur.next!=null) {
     cur = cur.next;
}

第四步:将新的结点连接到尾结点后面即可

cur.next = node;

完整的尾插法代码:

public void addLast(int data) {
        //尾插
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while(cur.next!=null) {
            cur = cur.next;
        }
        cur.next = node;
    }

(3)随机位置插入

public void add(int index, int data)

随机位置插入,需要用户指定插入的位置和值;所以需要讨论以下的情况

第一步:创造新的结点

ListNode node = new ListNode(data);

第二步:检查用户指定插入的位置是否合法

if(index < 0 || index > size()) {
      System.out.println("插入位置不合法");
      return;
}

第三步:检查链表是否为空

if(head == null) {
      head = node;
      return;
}

第四步:检查是否为头插法

如果是头插法就直接调用头插法就可以,不需要再浪费时间去写这个代码。尾插法需要单独考虑,和普通插入当成一种即可。

if(index == 0) {
       addFirst(data);
       return;
}

第五步:找到插入位置的前一个结点

在单链表中,只能找前一个的位置,如果找的是后一个位置,将无法获取前结点的信息

int count = index-1;
ListNode cur = head;
while(count > 0) {
      cur = cur.next;
      count--;
}

此时的cur指向插入位置的前一个结点

第六步:插入新的结点

插入新的结点都是要求连接后面,再连接前面

node.next = cur.next;
cur.next = node;

完整代码:

public void add(int index, int data) {
        //指定位置插入
        ListNode node = new ListNode(data);
        ListNode cur = head;
        //1.检查位置是否合法
        if(index < 0 || index > size()) {
            System.out.println("插入位置不合法");
            return;
        }
        //2.空链表情况
        if(head == null) {
            head = node;
            return;
        }
        //3.头插法情况(index = 0)
        if(index == 0) {
            addFirst(data);
            return;
        }
        //4.找前位置
        int count = index-1;
        while(count > 0) {
            cur = cur.next;
            count--;
        }
        //5.插入数据
        node.next = cur.next;
        cur.next = node;
    }
2.打印链表

打印链表比较简单,就是需要将链表遍历一遍即可,同样的道理,不能动head

public void show() {
        //打印
        ListNode cur = head;
        while(cur!=null) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
    }
3.删除数据

删除数据分为两种:一种是删除一个key结点;另一种是删除所以的key结点。删除的参数都是根据结点的值来判断

下面我们一起来查看这两种的代码和思路

(1)删除第一个key结点

第一步:判断是否为空链表

如果是空链表的情况,无论如果都无法删除,直接返回就好

if(head == null) {
       System.out.println("链表为空,无法删除");
       return;
 }

第二步:单独考虑头结点是否是目标结点

if(head.data == key) {
      head = head.next;
      return;
}

第三步:一边遍历链表一边删除结点

这里只需要遍历一遍就可以完成,不需要再找什么前结点;下面的代码是判断下一个结点是否为删除的结点,如果是,直接断开连接就好,不是则继续往下走

ListNode cur = head;
       while(cur.next!=null) {
         if(cur.next.data==key) {
             cur.next = cur.next.next;//删除操作
             return;
         }else {
              cur = cur.next;
        }
  }

第四步:链表中不存在key结点

System.out.println("没有该结点,删除失败!");

完整代码:

public void remove(int key) {
        //删除第一个key
        //1.空表
        if(head == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        //2.头结点就是目标结点
        if(head.data == key) {
            head = head.next;
            return;
        }
        //3.正常删除
        ListNode cur = head;
        while(cur.next!=null) {
            if(cur.next.data==key) {
                cur.next = cur.next.next;//删除操作
                return;
            }else {
                cur = cur.next;
            }
        }
        //4.找不到
        System.out.println("没有该结点,删除失败!");
    }

(2)删除所有的key结点

删除所有的结点是在删除一个key结点的前提下改进即可,删除一个key结点时,直接返回了,然后删除所有的key,我们不返回就好。下面分三步

第一步:判断是否为空链表

if(head == null) {
      System.out.println("链表为空,无法删除");
      return;
 }

第二步:删除头结点后面的所有key结点

下面的代码无法删除头结点,所以头结点的情况单独考虑并且放在最后面

ListNode cur = head.next;//需要删除的结点
        ListNode prev = head;//删除结点的前一个
        //2.删除中间的结点
        while(cur != null) {
            if(cur.data != key) {
                prev = cur;//让prev走到cur的位置
                cur = cur.next;//cur往下走
            }else {
              prev.next = cur.next;
              cur = cur.next;
            }
        }

第三步:删除头结点

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

完整代码:

public void removeAll(int key) {
        //删除所有key结点
        //1.检查空链表情况
        if(head == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        ListNode cur = head.next;//需要删除的结点
        ListNode prev = head;//删除结点的前一个
        //2.删除中间的结点
        while(cur != null) {
            if(cur.data != key) {
                prev = cur;//让prev走到cur的位置
                cur = cur.next;//cur往下走
            }else {
              prev.next = cur.next;
              cur = cur.next;
            }
        }
        //3.删除头结点
        if(head.data == key) {
            head = head.next;
        }
    }
4.查找某个元素

查找某个元素是否存在时,根据结点的值去查找

如果结点存在,返回true;不存在则返回false

public boolean contains(int key) {
        //查找key元素
        ListNode cur = head;
        while(cur!=null) {
            if(cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
5.检测链表大小

求链表的结点个数只需要遍历一遍链表即可,每走到一个结点的位置,计数器就家加1,最后返回即可

public int size() {
        //求链表大小
        ListNode cur = head;
        int count = 0;
        while(cur!=null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
6.完整的链表
public class MyList implements IList{
    class ListNode {
        public int data;//数据域
        public ListNode next;
        public ListNode(int data) {
            this.data = data;
        }
    }
    public ListNode head;//定位头的位置
    @Override
    public void addFirst(int data) {
        //头插
        ListNode node = new ListNode(data);
        node.next = head;//
        head = node;
    }
    @Override
    public void addLast(int data) {
        //尾插
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while(cur.next!=null) {
            cur = cur.next;
        }
        cur.next = node;
    }
    @Override
    public void add(int index, int data) {
        //指定位置插入
        ListNode node = new ListNode(data);
        //1.检查位置是否合法
        if(index < 0 || index > size()) {
            System.out.println("插入位置不合法");
            return;
        }
        //2.空链表情况
        if(head == null) {
            head = node;
            return;
        }
        //3.头插法情况(index = 0)
        if(index == 0) {
            addFirst(data);
            return;
        }
        //4.找前位置
        int count = index-1;
        ListNode cur = head;
        while(count > 0) {
            cur = cur.next;
            count--;
        }
        //5.插入数据
        node.next = cur.next;
        cur.next = node;
    }
    @Override
    public boolean contains(int key) {
        //查找key元素
        ListNode cur = head;
        while(cur!=null) {
            if(cur.data == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    @Override
    public void remove(int key) {
        //删除第一个key
        //1.空表
        if(head == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        //2.头结点就是目标结点
        if(head.data == key) {
            head = head.next;
            return;
        }
        //3.正常删除
        ListNode cur = head;
        while(cur.next!=null) {
            if(cur.next.data==key) {
                cur.next = cur.next.next;//删除操作
                return;
            }else {
                cur = cur.next;
            }
        }
        //4.找不到
        System.out.println("没有该结点,删除失败!");
    }
    @Override
    public void removeAll(int key) {
        //删除所有key结点
        //1.检查空链表情况
        if(head == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        ListNode cur = head.next;//需要删除的结点
        ListNode prev = head;//删除结点的前一个
        //2.删除中间的结点
        while(cur != null) {
            if(cur.data != key) {
                prev = cur;//让prev走到cur的位置
                cur = cur.next;//cur往下走
            }else {
              prev.next = cur.next;
              cur = cur.next;
            }
        }
        //3.删除头结点
        if(head.data == key) {
            head = head.next;
        }
    }
    @Override
    public int size() {
        //求链表大小
        ListNode cur = head;
        int count = 0;
        while(cur!=null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public void clear() {
        //清空链表
        head = null;
    }
    @Override
    public void show() {
        //打印
        ListNode cur = head;
        while(cur!=null) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
    }
 
}

接口:

public interface IList {
    public void addFirst(int data);//头插
    public void addLast(int data);//尾插
    public void add(int index,int data);//任意位置插入
    public boolean contains(int key);//检查key元素是否存在
    public void remove(int key);//删除第一个key
    public void removeAll(int key);//删除所有key
    public int size();//求链表的长度
    public void clear();//清空链表
    public void show();//打印链表
}

实例化链表对象:

public static void main(String[] args) {
        MyList myList = new MyList();//实例化链表对象
        myList.addLast(8);
        myList.addLast(1);
        myList.addLast(4);
        myList.show();
    }

本节单链表的实现就到这里了,快去自己模拟实现一下吧!

相关文章
|
3天前
|
算法 索引
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
【数据结构与算法 | 基础篇】[链表专题]力扣141, 142
|
3天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣82
【数据结构与算法 | 基础篇】[链表专题]力扣82
|
3天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
【数据结构与算法 | 基础篇】[链表专题]力扣21, 234
|
3天前
|
算法
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
【数据结构与算法 | 基础篇】[链表专题]力扣LCR077, 83
|
3天前
|
存储 算法
【数据结构与算法 | 基础篇】[链表专题]力扣206, 203, 19
【数据结构与算法 | 基础篇】[链表专题]力扣206, 203, 19
|
4天前
|
C语言 C++ 索引
力扣 138. 随机链表的复制
力扣 138. 随机链表的复制
|
10天前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
16 4
|
10天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
12 0
|
10天前
|
算法 索引
【刷题】滑动窗口精通 — Leetcode 30. 串联所有单词的子串 | Leetcode 76. 最小覆盖子串
经过这两道题目的书写,相信大家一定深刻认识到了滑动窗口的使用方法!!! 下面请大家继续刷题吧!!!
16 0

热门文章

最新文章