当前位置：首页 > news >正文

【一起学数据结构与算法】快速教你了解并实现单链表

news 来源：原创 2024/5/2 18:07:45

前言
一、单链表的概念
二、单链表内一些方法的实现
- 2.1 单链表长什么样子？
- 2.2 创建单链表
- 2.3 打印单链表
- 2.4 查找是否包含关键字key是否在单链表中
- 2.5 得到单链表的长度
- 2.6 addFirst -- 头插
- 2.7 addLast -- 尾插
- 2.8 addIndex -- 任意位置插入
- 2.9 remove -- 删除第一次出现的key
- 2.10 removeAllkey -- 删除所有值为key的结点
- 2.11 清空单链表
三、MyLinkedList.java
四、Test.java

前言

此篇是对单链表知识的学习和实现，基本上大体的方法实现和思路都已经表达，如果有不对的地方，还请各位大佬多多指教！

一、单链表的概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

二、单链表内一些方法的实现

2.1 单链表长什么样子？

在这里插入图片描述
像上面这样式的就是一种单链表！

由上图可以看出我们一些属性来表示单链表！

class ListNode {
    public int val;
    public ListNode next;

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

2.2 创建单链表

创建链表之前我们需要定义一个成员变量head表示链表的头结点！

 //成员变量
    public ListNode head;//链表的头引用

由于咱们是初步学习单链表，所有咱们就简单的创建的单链表

public void createList() {

        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;

    }

2.3 打印单链表

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

为什么会定义一个cur来指向head了？
那是因为如果拿head来遍历链表，那么最后head就指向了null，就找不到链表的头了，所以使用cur来完成操作！

2.4 查找是否包含关键字key是否在单链表中

我们只需要拿cur去遍历链表，看cur是否等于key，如果有就返回true，没有就返回false。
实现cur遍历的过程的代码就是：cur = cur.next;

//查找是否包含关键字key是否在单链表中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

2.5 得到单链表的长度

一样的操作，此处通过定义一个count作为计数器，直到cur遍历完整个链表就停止.

//得到单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

2.6 addFirst – 头插

//头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
        /*if (this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }*/
    }

在这里插入图片描述

2.7 addLast – 尾插

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

在这里插入图片描述

2.8 addIndex – 任意位置插入

/**
     * 找到index - 1 位置结点的地址
     * @param index
     * @return
     */
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入，第一个数据结点为0号下标
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法!");
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

在这里插入图片描述

2.9 remove – 删除第一次出现的key

 /**
     * 找到要删除关键字的前驱
     * @param key
     * @return
     */
    public ListNode searchPrev(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现的关键字key的结点
    public void remove(int key) {
        if (this.head == null) {
            System.out.println("单链表为空，不能删除！");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if (cur == null) {
            System.out.println("没有你要删除的结点！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

在这里插入图片描述

2.10 removeAllkey – 删除所有值为key的结点

//删除所有值为key的结点
    public ListNode removeAllKey(int key) {
        if (this.head == null) return null;

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后处理头
        if (this.head.val == key) {
            this.head = this.head.next;
        }
        return this.head;
    }

1.如果先处理头，则需要写成循环，因为当链表所有结点都是待删除的情况时，一个if条件语句处理不了

2.while循环里面的条件不能写成cur.next == null，因为removeSubOne函数如果没找到待删除的结点，它返回的是一个null，如果写成cur.next != null，则可能会报空指针异常

2.11 清空单链表

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

三、MyLinkedList.java

import java.util.LinkedList;

@SuppressWarnings({"all"})

class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
public class MyLinkedList {

    //成员变量
    public ListNode head;//链表的头引用

    public void createList() {

        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1;

    }

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

    //查找是否包含关键字key是否在单链表中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.head;
        this.head = node;
        /*if (this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }*/
    }

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

    /**
     * 找到index - 1 位置结点的地址
     * @param index
     * @return
     */
    public ListNode findIndex(int index) {
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //任意位置插入，第一个数据结点为0号下标
    public void addIndex(int index, int data) {
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法!");
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 找到要删除关键字的前驱
     * @param key
     * @return
     */
    public ListNode searchPrev(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    //删除第一次出现的关键字key的结点
    public void remove(int key) {
        if (this.head == null) {
            System.out.println("单链表为空，不能删除！");
            return;
        }
        if (this.head.val == key) {
            this.head = this.head.next;
            return;
        }
        ListNode cur = searchPrev(key);
        if (cur == null) {
            System.out.println("没有你要删除的结点！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }

    //删除所有值为key的结点
    public ListNode removeAllKey(int key) {
        if (this.head == null) return null;

        ListNode prev = this.head;
        ListNode cur = this.head.next;

        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后处理头
        if (this.head.val == key) {
            this.head = this.head.next;
        }
        return this.head;
    }

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

四、Test.java

public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
       /* myLinkedList.createList();
        myLinkedList.display();
        boolean flag = myLinkedList.contains(34);
        System.out.println(flag);
        int size = myLinkedList.size();
        System.out.println(size);*/
        myLinkedList.addFirst(12);
        myLinkedList.addFirst(23);
        myLinkedList.addLast(39);
        myLinkedList.addLast(37);
        myLinkedList.addIndex(0,99);
        myLinkedList.addIndex(5,99);
        myLinkedList.addIndex(3,99);
        myLinkedList.display();
        myLinkedList.remove(12);
        myLinkedList.removeAllKey(99);
        myLinkedList.display();
        myLinkedList.clear();
        myLinkedList.display();

    }
}