devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】手撕单链表_手撕单链表的实现

作者：weixin_40725706 | 2024-06-02 07:13:01

赞

踩

手撕单链表的实现

在这里插入图片描述
希望通过博客和大家相互交流，相互学习，如有错误，请评论区指正

文章目录

一、什么是链表

顺序表在空间利用，系统消耗，插入元素方面都是存在缺陷的。而链表是最常用的动态存储方法，克服了顺序表的缺点。

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

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储指向下一个结点的引用域


链表的结构很多，有以下6种情况，组合起来有8种

  • 有头、无头
  • 单向、双向
  • 循环、非循环

在这8种情况中，我们一般重点学习其中的2种，无头单向非循环链表和无头双向循环链表

二、手撕链表

这里实现无头单向非循环链表

属性定义

我们需要有链表结点和链表对象，如下：

结点对象
public class Node {
    public int data;
    public Node next;
}

  • 1
  • 2
  • 3
  • 4
构造方法
public Node(int data) {
	this.data = data;    // 注意要用 this， 里面直接写data的话就是形参data
	this.next = null;
}

  • 1
  • 2
  • 3
  • 4
链表对象
public class MyLinkedList {
    public Node head;
}

  • 1
  • 2
  • 3
构造方法
public MyLinkedList() {
    this.head = null;
}

  • 1
  • 2
  • 3

链表的实现

//头插
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();
public void display();
public void clear();

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

注意：在实现这些方法的时候，要注意遍历链表 while 循环判断条件应该是 cur.next != null 还是 cur != null

插入删除元素的时候考虑边界条件及特殊情况（只有一个结点、空结点等）

头插
public void addFirst(int data) {
    Node newNode = new Node(data);
    if (this.head == null) {     // 当为空链表时，只需要让head指向该结点即可
        head = newNode;        
        return;
    }
    newNode.next = head;
    head = newNode;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
尾插

注意当链表为空的时候特殊处理. 不为空时，通过遍历链表的方式找尾，然后再插入

public void addLast(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        return;
    }
    Node cur = head;
    while (cur.next != null) {
        cur = cur.next;
    }
    cur.next = newNode;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
得到单链表的长度
public int size() {
    int count = 0;
    Node cur = this.head;
    while (cur != null) {
        cur = cur.next;
        count++;
    }
    return count;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
任意位置插入

设定第一个数据节点为0号下标，要注意考虑会有头插，尾插，下标不合法等情况

public void addIndex(int index, int data) {
    if (index < 0 || index > this.size()) {
        throw new RuntimeException("index" + ":" + index);
    }
    Node newNode = new Node(data);
    if (index == 0) {    // 头插
        this.addFirst(data);
        return;
    }
    if (index == this.size()) {   // 尾插
        this.addLast(data);
        return;
    }
    Node cur = this.head;
    while (index - 1 != 0) {
        cur = cur.next;
        index--;
    }
    newNode.next = cur.next;
    cur.next = newNode;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
查找是否包含关键字key

遍历链表，将结点数据和key进行比较

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
删除第一次出现关键字为key的节点

遍历链表，找到第一个为key的结点然后删除,要考虑链表为空，头删，等特殊情况

public void remove(int key) {
    if (this.head == null) {
        return;
    }
    if (head.data == key) {   // 头删
        head = head.next;
        return;
    }
    Node cur = this.head;
    while (cur.next != null) {
        if (cur.next.data == key) {
            break;
        }
        cur = cur.next;
    }
    if (cur.next != null) {
        cur.next = cur.next.next;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
打印单链表
public void display() {
    Node cur = this.head;
    while (cur != null) {
        System.out.print(cur.data + "->");
        cur = cur.next;
    }
    System.out.print("null");
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
清空链表

在用完链表之后使用clear() 方法防止发生内存泄漏（查看进程号jps, 重定向 jmap -histo:live 6666 > e:\niubi.txt）

public void clear() {
    this.head = null;
}

  • 1
  • 2
  • 3
删除所有值为key的节点

注意：1. prev到底什么时候才往后跳， 第一个结点不应该刚开始就判断，而应该后面的都删完了之后再判断第一个结点

public void removeAll(int key) {
    if (this.head == null) {
        return;
    }
    Node prev = this.head;
    Node cur = this.head.next;
    while (cur != null) {
        if (cur.data == key) {
            prev.next = cur.next;
            cur = cur.next;
        } else {
            prev = cur;
            cur = cur.next;      // 不是key，cur和prev都往后跳
        }
    }
    if (this.head.data == key) {
        this.head = this.head.next;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

2. 双向链表

这里以双向无头非循环链表为例来介绍，如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Bvzi6qI-1641391981418)(C:\Users\lycre\AppData\Roaming\Typora\typora-user-images\image-20220105182248704.png)]

属性定义

结点对象及构造方法和单线表相同

链表对象

链表对象多一个tail属性，指向链表的尾结点

public class MyLinkedList{
    public Node head;
    public Node tail;
}

  • 1
  • 2
  • 3
  • 4
构造方法

无参构造方法

public MyLinkedList() {
    this.head = null;
    this.tail = null;
}

  • 1
  • 2
  • 3
  • 4

链表的实现

//头插法
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();
//打印链表
public void display();
//清空链表，释放内存
public void clear();

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
头插

头插的过程中要注意空链表的情况

public void addFirst(int data) {
    Node newNode = new Node(data);
    if (this.head == null) {    // 链表为空时
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
尾插
public void addLast(int data) {
    Node newNode = new Node(data);
    if (this.head == null) {   // 链表为空的情况
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.prev = tail;
        this.tail.next = newNode;
        this.tail = newNode;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
得到链表的长度
public int size() {
    int count = 0;
    Node cur = this.head;
    while (cur != null) {
        count++;
        cur = cur.next;
    }
    return count;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
任意位置插入

在任意位置插入元素需要考虑的情况会比较多，我们应该先将可能的情况都罗列出来，再写，避免忽略一些情况

注意对index有效性进行判断

public void addIndex(int index,int data) {
    if (index < 0 || index > this.size()) {
        throw new RuntimeException("index : "  + index);
    }
    Node newNode = new Node(data);
    if (index == 0) {
        if (this.head == null) {   // 头插
            this.head = newNode;
            this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }
    } else if (index == this.size()) {   // 尾插
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
    } else {
        Node cur = this.head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        Node prevNode = cur.prev;
        newNode.next = cur;
        newNode.prev = prevNode;
        prevNode.next = newNode;
        cur.prev = newNode;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
查找是否包含关键字key

直接遍历链表，逐一对比

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
删除第一次出现关键字为key的结点

涉及到头删，尾删，空链表等情况

public void remove(int key) {
    if (this.head == null) {
        return;
    }
    Node cur = this.head;
    while (cur != null) {        // 找第一个为key的结点
        if (cur.data == key) {
            break;
        }
        cur = cur.next;
    } 
    if (cur == null) {
        return;          //没找到，直接返回
    }
    if (cur == this.head) {       // 头删
        this.head = head.next;
        this.head.prev = null;  
        return;
    }
    if (cur == this.tail) {     // 尾删
        cur.prev.next = null;
        this.tail = cur.prev;
        return;
    }
    Node prevNode = cur.prev;
    Node nextNode = cur.next;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
删除所有值为key的节点、
public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    Node prevNode = this.head;
    Node cur = this.head.next;
    while (cur != null) {
        if (cur.data == key) {
            prevNode.next = cur.next;
            cur = cur.next;
            if (cur == null) {
                this.tail = prevNode;     // 最后一个结点值为key
            } else {
                cur.prev = prevNode;
            }
        } else {
            cur = cur.next;
            prevNode = prevNode.next;
        }
    }
    if (this.head.data == key) {
        this.head = this.head.next;
        if (this.head == null) {
            this.tail = null;      // 注意当链表中所有元素均为key时，在最后不仅要判断head，也要改tail
            return;
        }
        this.head.prev = null;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
打印链表
public void display() {
    Node cur = this.head;
    while (cur != null) {
        System.out.print(cur.data + "->");
        cur = cur.next;
    }
    System.out.print("null");
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
清空链表，释放内存
public void clear() {
    if (this.head == null) {
        return;
    }
    Node cur = this.head;
    Node nextNode;
    while (cur != null) {
        nextNode = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = nextNode;
    }
    this.tail = null;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

注意清空双向链表和单向链表是有很大区别的，不能直接将head置为null，因为后面的结点还保存这前面结点的引用，所以我们应该要将所有结点的next域和prev域置空

欢迎大家关注！！！

一起学习交流 ！！！

让我们将编程进行到底！！！

--------------整理不易，请三连支持------------------

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/661731
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号