数据结构 - 单链表

文章目录

目录

文章目录

一、什么是链表?

线性表:

顺序表:

二、链表的分类和实现

分类:

实现:

1.创建节点类

2.创建单链表 

1.addTail(尾增)

 

2.删除节点值为key的第一个节点

 3.插入节点(在指定位置)

4.获取链表长度 

总结

---

大家好,这篇博客给大家讲一下什么是链表以及单链表的实现过程

---

一、什么是链表?

再讲解什么是链表时,先给大家讲一下大体上的分类线性表和顺序表

线性表:

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：链表、栈、队列... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。

可以看到链表在内存中并不是连续的,只是在逻辑上是连续的,链表中的节点见缝插针般的在内存中存储 

顺序表:

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成 数据的增删查改。

---

二、链表的分类和实现

分类:

链表根据是否包含头结点来分可以分为两类,根据是否循环来分也可以分为两类

其中循环和非循环相对来说差别不大,下面我们将围绕是否包含头节点来进行谈论

问题1:含头节点的链表和不含头节点的链表有什么不同?

带头结点的链表的第一个节点不存数据,实现起来相对比较容易

不带头结点的第一个节点就是数据节点,实现起来比带头结点的难一些,并且是刷题和面试的重点

下面我将带大家来实现最经典的单链表:不带头节点的非循环链表

实现:

思路分析:

1.创建节点类Node,用来表示链表中的节点

2.创建单链表 SingleList

3.实现方法 增,删,查.......

1.创建节点类

来思考一下节点类中应该存在的信息?

日常工作生活中节点中记录的信息是多种多样的,为了简单起见我们按最简单的来,即节点中只包含

val和指向下一个节点的指针next

class Node{
    public int val;
    public Node next;

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

2.创建单链表 

有了节点类,我们就可以把一个个节点组合起来,组合成为一个在逻辑上是连续的链表了

那么在单链表中应该存在什么呢?

首先应该有个头结点,要不然无法知道链表从哪里开始,也不能将链表作为参数传递出去

其次应该有构造方法,不然写这么个链表就会毫无意义

还有就是一些方法,基础代码给出,下面我们来一个一个实现方法

public class SingleListDemo {
    private Node head;

    public SingleListDemo(){
    }

}


class Node{
    public int val;
    public Node next;

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

1.addTail(尾增)

public void addTail(int val) {
    Node newNode = new Node(val);

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

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

    cur.next = newNode;
}

在这里我们可以延伸出在头部插入节点的情况,即将新的节点的next指针指向头结点,将头结点的指向更改为新的节点即可 

2.删除节点值为key的第一个节点

// 删除节点的Data值为key的第一个节点
public void DeleteKey(int key) {
    // 判断链表是否为空
    if (head == null) {
        System.out.println("链表为空");
        return;
    }
    // 判断第一个节点是否是要删除的节点
    if (head.val == key) {
        HeadDelete();
        return;
    }
    Node cur = head;
    while (cur.next != null) {
        if (cur.next.val == key) {
            cur.next = cur.next.next;
            return;
        }
        cur = cur.next;
    }
}

 拓展: 删除值为key的所有节点,要求时间复杂度不超过O(n)

// 法一 循环遍历
public void Delete(int Data) {
    if (head == null) {
        return;
    }
    while (head.val == Data) {
        head = head.next;
        if (head == null) {
            return;
        }
    }
    Node cur = head;// 定义临时节点代替头结点遍历链表并删除元素
    while (true) {
        if (cur.next == null) {
            return;
        }

        if (cur.next.val == Data) {
            System.out.println("删除成功!");
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }

}

// 法二 - 双指针
public void Delete2(int Data) {
    if (head == null) {
        return;
    }
    Node pre = head;
    Node cur = head.next;

    while (cur != null) {
        if (cur.val == Data) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    if (head.val == Data) {
        head = head.next;
    }
}

 3.插入节点(在指定位置)

// 在指定位置插入节点,第一个节点为0号下标
public void InsertAny(int index, int val) {
    // 判断链表下标是否合法
    if (index < 0 && index > getSize()) {
        System.out.println("下标不合法!");
        return;
    }
    if (index == 0) {
        HeadAdd(val);
        return;
    }
    Node node = new Node(val);
    Node cur = head;
    // 遍历链表找到下标为index-1的元素
    while (index > 1) {//index-1
        index--;
        cur = cur.next;
    }
    node.next = cur.next;
    cur.next = node;
}

4.获取链表长度 

public int getSize() {
    Node node = head;
    int size = 0;
    while (node != null) {
        node = node.next;
        size++;
    }
    return size;
} 

以上就是一些比较重要的方法了,下期见。 

---

总结

大家多多刷题吧,链表可是面试中笔试题的重点!