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

数据结构基础（三）链表

作者：2023面试高手 | 2024-03-27 00:26:37

赞

踩

数据结构基础（三）链表

链表（Linked List）是一种常见的线性数据结构，由一系列称为节点（Node）的元素组成，每个节点包含两部分：数据（Data）和指向下一个节点的引用（Pointer 或者 Link）。通过这种节点之间的指针连接起来，形成了链式结构

我们为什么需要链表

链表常 用于存储和组织数据。它的设计目的主要有以下几个方面的考虑：

  1. 动态内存分配：链表能够动态地分配内存空间，这意味着它可以根据需要动态地增加或减少元素，而不需要像数组一样预先指定大小。

  2. 灵活性：链表的插入和删除操作非常高效，时间复杂度为 O(1)，这是因为它不需要像数组那样进行元素的移动。

  3. 适应动态数据：链表适用于需要频繁插入和删除操作的场景，比如实现队列、栈等数据结构。

  4. 内存紧张：当内存紧张时，链表可以节省内存空间，因为它只在需要时分配内存。

  5. 不连续内存：链表的节点不需要在内存中连续存储，这使得链表能够有效地利用零散的内存空间。

  6. 支持不同长度的元素：链表中的每个节点都包含一个指向下一个节点的指针，因此节点之间的大小不必相等，可以存储不同长度的元素。

  7. 简单实现：链表相对于其他数据结构（比如树）来说，实现起来比较简单，不需要复杂的数据结构和算法。

相对于数组而言，链表是一种非常灵活和高效的数据结构，特别适用于动态数据和需要频繁插入、删除操作的场景。在编程中，链表常用于实现各种数据结构，如队列、栈、图等，并且在很多算法中都有着广泛的应用。

手动实现链表

  • Java内置了 java.util.LinkedList 类，它是 Java 标准库中的一部分，用于表示双向链表（Doubly Linked List）。

我们可以参照该类进行设计

需求分析

链表是由一个个数据节点构成，换句话说，我们将每条数据储存在链表中的每一个数据节点中。同时每个节点要负责帮助我们找到下一个节点在哪里。所以我们需要一个内置Node类，它的内部有一个数据，一个节点指针。

     private class Node {
        E data;
        Node next;//下一个节点的地址

        Node(E data) {
            this.data = data;
            this.next = null;
        }
    }


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

回到链表本身，我们需要记录整个链表的大小，size， 不仅如此，我也要一个头指针帮我定位整个链表的起始点。

public class MyLinkedList<E> {
    private class Node {
        E data;
        Node next;

        Node(E data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;
    private int size;

    public MyLinkedList() {
        head = null;
        size = 0;
    }
}

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

功能实现

  • 1.添加元素

这个功能很容易理解，不过呢，我们肯定不能满足仅仅append元素。应该允许我们指定位置插入

        // 在链表末尾添加元素
    public void add(E data) {
        add(size, data);
    }

    /**
     * 在指定位置插入一个元素。
     * @param index 插入位置的索引，从0开始。
     * @param data 要插入的元素。
     * @throws IndexOutOfBoundsException 如果索引小于0或大于当前列表大小，则抛出异常。
     */
    public void add(int index, E data) {
        // 检查索引是否超出范围
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        Node newNode = new Node(data); // 创建新节点
        // 当索引为0时，将新节点插入到链表头部
        if (index == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            // 遍历链表，找到插入位置的前一个节点
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        size++; // 更新列表大小
    }

  • 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
  • 32
  • 2.删除元素

有增加就需要有删除

        /**
     * 删除链表中指定位置的元素。
     * @param index 要删除的元素的位置索引。
     * @throws IndexOutOfBoundsException 如果索引超出链表范围，则抛出异常。
     */
    public void remove(int index) {
        // 检查索引是否超出链表范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        // 如果删除的是头节点
        if (index == 0) {
            head = head.next;
        } else {
            // 遍历找到要删除节点的前一个节点
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            // 跳过要删除的节点，重新连接链表
            current.next = current.next.next;
        }
        size--; // 更新链表大小
    }


    /**
     * 删除链表中指定数据的元素。
     * @param data 要删除的元素数据。
     */
    public void remove(E data) {
        // 如果链表为空，则直接返回
        if (head == null) {
            return;
        }
        // 如果头节点数据与要删除的数据相等，则将头节点指向下一个节点，并更新大小
        if (head.data.equals(data)) {
            head = head.next;
            size--;
            return;
        }
        // 从第二个节点开始遍历链表，寻找要删除的数据
        Node current = head;
        while (current.next != null) {
            // 如果找到要删除的数据，则跳过该节点，并更新大小
            if (current.next.data.equals(data)) {
                current.next = current.next.next;
                size--;
                return;
            }
            current = current.next;
        }
    }

  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 3.查询元素
    /**
     * 获取链表中指定位置的元素。
     *
     * @param index 要获取元素的位置，从0开始计数。
     * @return 链表中指定位置的元素。
     * @throws IndexOutOfBoundsException 如果指定位置超出链表范围（小于0或大于等于链表长度）。
     */
    public E get(int index) {
        // 检查索引是否超出链表范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        Node current = head;
        // 遍历链表，直到达到指定位置
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data; // 返回指定位置的元素
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 4.其他方法
    // 返回链表的大小
    public int size() {
        return size;
    }

    // 清空链表
    public void clear() {
        head = null; //垃圾回收器会自动清理内存
        size = 0;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

全部代码

public class MyLinkedList<E> {
    private class Node {
        E data;
        Node next;

        Node(E data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;
    private int size;

    public MyLinkedList() {
        head = null;
        size = 0;
    }

    // 在链表末尾添加元素
    public void add(E data) {
        add(size, data);
    }

    /**
     * 在指定位置插入一个元素。
     * @param index 插入位置的索引，从0开始。
     * @param data 要插入的元素。
     * @throws IndexOutOfBoundsException 如果索引小于0或大于当前列表大小，则抛出异常。
     */
    public void add(int index, E data) {
        // 检查索引是否超出范围
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        Node newNode = new Node(data); // 创建新节点
        // 当索引为0时，将新节点插入到链表头部
        if (index == 0) {
            newNode.next = head;
            head = newNode;
        } else {
            // 遍历链表，找到插入位置的前一个节点
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        size++; // 更新列表大小
    }


    // 返回链表的大小
    public int size() {
        return size;
    }

    // 清空链表
    public void clear() {
        head = null;
        size = 0;
    }

    /**
     * 获取链表中指定位置的元素。
     *
     * @param index 要获取元素的位置，从0开始计数。
     * @return 链表中指定位置的元素。
     * @throws IndexOutOfBoundsException 如果指定位置超出链表范围（小于0或大于等于链表长度）。
     */
    public E get(int index) {
        // 检查索引是否超出链表范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        Node current = head;
        // 遍历链表，直到达到指定位置
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data; // 返回指定位置的元素
    }

    /**
     * 删除链表中指定位置的元素。
     * @param index 要删除的元素的位置索引。
     * @throws IndexOutOfBoundsException 如果索引超出链表范围，则抛出异常。
     */
    public void remove(int index) {
        // 检查索引是否超出链表范围
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        // 如果删除的是头节点
        if (index == 0) {
            head = head.next;
        } else {
            // 遍历找到要删除节点的前一个节点
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            // 跳过要删除的节点，重新连接链表
            current.next = current.next.next;
        }
        size--; // 更新链表大小
    }


    /**
     * 删除链表中指定数据的元素。
     * @param data 要删除的元素数据。
     */
    public void remove(E data) {
        // 如果链表为空，则直接返回
        if (head == null) {
            return;
        }
        // 如果头节点数据与要删除的数据相等，则将头节点指向下一个节点，并更新大小
        if (head.data.equals(data)) {
            head = head.next;
            size--;
            return;
        }
        // 从第二个节点开始遍历链表，寻找要删除的数据
        Node current = head;
        while (current.next != null) {
            // 如果找到要删除的数据，则跳过该节点，并更新大小
            if (current.next.data.equals(data)) {
                current.next = current.next.next;
                size--;
                return;
            }
            current = current.next;
        }
    }


    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        list.add(1, 4); // 在索引1处插入元素4

        System.out.println("Size of LinkedList after insertion: " + list.size());
        System.out.println("Element at index 1: " + list.get(1));
    }
}

  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151

双向链表

双向链表是一种链表数据结构，其中每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点。与单向链表相比更方便双向遍历和删除插入节点

其实实现上和上面一本一样，只是需要考虑一个prev指针


/**
 * MyLinkedList类，实现一个双向链表。
 * @param <E> 链表元素的类型。
 */
public class MyLinkedList<E> {
    /**
     * 链表节点内部类。
     * 包含数据、前向指针和后向指针。
     */
    private class Node {
        E data;
        Node prev;
        Node next;

        /**
         * 节点构造函数。
         * @param data 节点存储的数据。
         */
        Node(E data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    private Node head; // 链表头节点
    private Node tail; // 链表尾节点
    private int size; // 链表大小

    /**
     * 链表构造函数，初始化链表。
     */
    public MyLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 在链表末尾添加元素。
     * @param data 要添加的数据。
     */
    public void add(E data) {
        add(size, data);
    }

    /**
     * 在指定位置插入元素。
     * @param index 插入的位置。
     * @param data 要插入的数据。
     * @throws IndexOutOfBoundsException 如果索引超出范围，则抛出异常。
     */
    public void add(int index, E data) {
        // 检查索引是否有效
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        Node newNode = new Node(data);
        // 处理头节点插入和尾节点插入的情况
        if (index == 0) {
            // 处理在头部插入的情况
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                newNode.next = head;
                head.prev = newNode;
                head = newNode;
            }
        } else if (index == size) {
            // 处理在尾部插入的情况
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        } else {
            // 在中间位置插入
            Node current = head;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            newNode.prev = current;
            current.next.prev = newNode;
            current.next = newNode;
        }
        size++;
    }


    /**
     * 返回链表的大小。
     * @return 链表中元素的数量。
     */
    public int size() {
        return size;
    }

    /**
     * 清空链表。
     * 将头尾指针置空，大小设为0。
     */
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    /**
     * 获取指定位置的元素。
     * @param index 要获取元素的位置。
     * @return 位置处的元素。
     * @throws IndexOutOfBoundsException 如果索引超出范围，则抛出异常。
     */
    public E get(int index) {
        // 检查索引是否有效
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        Node current = head;
        // 遍历链表，直到找到指定位置的元素
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }


    /**
     * 删除指定位置的元素。
     * @param index 要删除的元素的位置。
     * @throws IndexOutOfBoundsException 如果提供的索引超出链表范围，则抛出异常。
     */
    public void remove(int index) {
        // 检查索引是否有效
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index out of bounds");
        }
        // 根据索引位置的不同，分别处理删除头节点、尾节点和中间节点的情况
        if (size == 1) { // 当链表只有一个元素时，删除后同时将头尾指针置为null
            head = null;
            tail = null;
        } else if (index == 0) { // 删除头节点
            head = head.next;
            head.prev = null;
        } else if (index == size - 1) { // 删除尾节点
            tail = tail.prev;
            tail.next = null;
        } else { // 删除中间的节点
            Node current = head;
            for (int i = 0; i < index; i++) {
                current = current.next;
            }
            // 断开选定节点的前后连接
            current.prev.next = current.next;
            current.next.prev = current.prev;
        }
        size--; // 链表大小减1
    }


    /**
     * 删除链表中第一个匹配给定数据的节点。
     * @param data 要删除的数据。
     * 该方法首先检查链表是否为空，若为空则直接返回。
     * 接着区分三种情况：删除头节点、删除尾节点、删除中间节点。
     * 对于删除头节点和尾节点，需要更新头尾指针。
     * 对于删除中间节点，需要更新前后节点的指针。
     * 删除操作完成后，链表长度减一。
     */
    public void remove(E data) {
        if (head == null) { // 链表为空，直接返回
            return;
        }
        // 处理删除头节点和尾节点的情况，以及中间节点的情况
        if (head.data.equals(data)) { // 删除头节点
            head = head.next;
            if (head != null) { // 更新头节点的前指针
                head.prev = null;
            }
            size--;
            return;
        }
        if (tail.data.equals(data)) { // 删除尾节点
            tail = tail.prev;
            tail.next = null; // 更新尾节点的后指针
            size--;
            return;
        }
        Node current = head; // 从头开始查找要删除的节点
        while (current != null) {
            if (current.data.equals(data)) { // 找到要删除的节点
                current.prev.next = current.next; // 更新前节点的后指针
                current.next.prev = current.prev; // 更新后节点的前指针
                size--;
                return;
            }
            current = current.next; // 继续查找下一个节点
        }
    }


    // 主函数，示例使用
    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);

        list.add(1, 4); // 在索引1处插入元素4

        System.out.println("Size of LinkedList after insertion: " + list.size());
        System.out.println("Element at index 1: " + list.get(1));
    }
}

  • 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
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215

总结

我们自己写的链表是一个简单的实现，用于演示链表的基本操作和原理，并作为学习链表数据结构的起点。通过自己动手实现链表，可以加深对链表的理解，并提升编程能力。作为学习链表数据结构的起点，它相比于标准库中的链表实现可能存在一些局限性，但非常适用于学习和理解链表的基本概念。

在这里插入图片描述

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

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

  

闽ICP备14008679号