LinkedList和链表-EW帮帮网

在我们学习ArrayList时,就发现ArrayList有一定缺陷: 在插入或删除任意元素时,就需要将该元素的后序所有元素向后移或者向前移,这样的时间复杂度为: O(N)

所以ArrayList不适合做任意位置的多次插入和删除操作

所以我们又引入了链式存储结构,即链表

链表

基础概念

是一种物理存储结构上非连续,但是数据的逻辑结构连续(通过引入连接来实现)的存储结构,比如火车,就是由一节节车厢连接起来的,车厢就可以看作节点

在使用链表的时候,我们也需要注意几点:

链式结构在逻辑上是连续的,但是物理上是不一定连续的
节点一般都是从堆上申请出来的
从堆上申请的空间,是按照一定的策略来分配,也就是说两次申请的空间可能连续也可能不连续

同时链表只是一种形式,所以他也有很多种结构

结构示例

单向/双向链表

带头/不带头链表

循环/非循环链表

以下是重点掌握对象

无头单向非循环链表

结构较简单,一般不会单独用来存数据,一般是作为其他数据结构的子结构

无头双向链表

链表实现

实现的是无头单向非循环链表

构造节点

private Node head; // 链表的头节点
private int size;  // 链表的长度

// 内部节点类
private static class Node {
    int data;     // 节点存储的数据
    Node next;    // 指向下一个节点的引用

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

头插法

// 头插法
public void addFirst(int data) {
    Node newNode = new Node(data);
    newNode.next = head; // 新节点的next指向当前头节点
    head = newNode;     // 更新头节点为新节点
    size++;             // 链表长度增加
}

尾插法

public void addLast(int data) {
    Node newNode = new Node(data);
    if (head == null) { // 如果链表为空，直接设置为头节点
        head = newNode;
    } else {
        Node current = head;
        while (current.next != null) { // 遍历到链表末尾
            current = current.next;
        }
        current.next = newNode; // 在末尾插入新节点
    }
    size++; // 链表长度增加
}

任意位置插入

public void addIndex(int index, int data) {
    if (index < 0 || index > size) { // 检查索引是否合法
        throw new IndexOutOfBoundsException("Index is out of bounds");
    }
    if (index == 0) {
        addFirst(data); // 如果索引为0，调用头插法
    } else if (index == size) {
        addLast(data);  // 如果索引为链表长度，调用尾插法
    } else {
        Node newNode = new Node(data);
        Node current = head;
        for (int i = 0; i < index - 1; i++) { // 遍历到索引的前一个节点
            current = current.next;
        }
        newNode.next = current.next; // 新节点的next指向当前节点的next
        current.next = newNode;    // 当前节点的next指向新节点
        size++; // 链表长度增加
    }
}

查找是否包含关键字key

public boolean contains(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            return true; // 找到关键字
        }
        current = current.next;
    }
    return false; // 未找到关键字
}

删除第一次出现关键字为key的节点

public void remove(int key) {
    if (head == null) { // 链表为空，直接返回
        return;
    }
    if (head.data == key) { // 如果头节点是要删除的节点
        head = head.next; // 更新头节点
        size--; // 链表长度减少
        return;
    }
    Node current = head;
    while (current.next != null) { // 遍历链表
        if (current.next.data == key) {
            current.next = current.next.next; // 删除节点
            size--; // 链表长度减少
            return;
        }
        current = current.next;
    }
}

删除所有值为key的节点

public void removeAllKey(int key) {
    while (head != null && head.data == key) { // 处理头节点为key的情况
        head = head.next;
        size--;
    }
    if (head == null) { // 如果链表为空，直接返回
        return;
    }
    Node current = head;
    while (current.next != null) { // 遍历链表
        if (current.next.data == key) {
            current.next = current.next.next; // 删除节点
            size--; // 链表长度减少
        } else {
            current = current.next;
        }
    }
}

得到单链表的长度

public int size() {
    return size;
}

清空链表

public void clear() {
    head = null; // 将头节点置为空
    size = 0;   // 链表长度重置为0
}

显示链表内容

public void display() {
    Node current = head;
    while (current != null) { // 遍历链表
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null"); // 链表末尾
}

输出结果

public static void main(String[] args) {
    LinkedTest list = new LinkedTest();
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.addIndex(2, 5);
    list.display(); // 输出: 0 -> 1 -> 5 -> 2 -> 3 -> null

    System.out.println("Contains 2: " + list.contains(2)); // 输出: true
    list.remove(2);
    list.display(); // 输出: 0 -> 1 -> 5 -> 3 -> null

    list.addLast(3);
    list.addLast(3);
    list.removeAllKey(3);
    list.display(); // 输出: 0 -> 1 -> 5 -> null

    System.out.println("Size: " + list.size()); // 输出: 3
    list.clear();
    list.display(); // 输出: null
}

LinkedList

基本概念

对于LinkedList的底层实现是双向链表

同时我们也要注意:

LinkedList实现了List接口
LinkedList的底层使用了双向链表
LinkedList没有实现RandomAccess接口,因为不支持随机访问
任意位置插入和删除元素时效率比较高,时间复杂度为 O(1)
当需要多次插入和删除操作时,我们可以使用LinkedList

模拟实现

构造节点

private Node head; // 链表的头节点
private Node tail; // 链表的尾节点
private int size;  // 链表的长度

// 内部节点类
private static class Node {
    int data;     // 节点存储的数据
    Node prev;    // 指向前一个节点的引用
    Node next;    // 指向下一个节点的引用

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

头插法

public void addFirst(int data) {
    Node newNode = new Node(data);
    if (head == null) { // 如果链表为空
        head = tail = newNode;
    } else {
        newNode.next = head; // 新节点的next指向当前头节点
        head.prev = newNode; // 当前头节点的prev指向新节点
        head = newNode;     // 更新头节点为新节点
    }
    size++; // 链表长度增加
}

尾插法

public void addLast(int data) {
    Node newNode = new Node(data);
    if (tail == null) { // 如果链表为空
        head = tail = newNode;
    } else {
        newNode.prev = tail; // 新节点的prev指向当前尾节点
        tail.next = newNode; // 当前尾节点的next指向新节点
        tail = newNode;     // 更新尾节点为新节点
    }
    size++; // 链表长度增加
}

任意位置插入

public void addIndex(int index, int data) {
    if (index < 0 || index > size) { // 检查索引是否合法
        throw new IndexOutOfBoundsException("Index is out of bounds");
    }
    if (index == 0) {
        addFirst(data); // 如果索引为0，调用头插法
    } else if (index == size) {
        addLast(data);  // 如果索引为链表长度，调用尾插法
    } else {
        Node newNode = new Node(data);
        Node current = head;
        for (int i = 0; i < index; i++) { // 遍历到索引的节点
            current = current.next;
        }
        newNode.prev = current.prev; // 新节点的prev指向当前节点的prev
        newNode.next = current;     // 新节点的next指向当前节点
        current.prev.next = newNode; // 当前节点的前一个节点的next指向新节点
        current.prev = newNode;      // 当前节点的prev指向新节点
        size++; // 链表长度增加
    }
}

查找是否包含关键字key

public boolean contains(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            return true; // 找到关键字
        }
        current = current.next;
    }
    return false; // 未找到关键字
}

删除第一次出现关键字为key的节点

public void remove(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            if (current == head) { // 如果要删除的是头节点
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    tail = null; // 如果链表只有一个节点
                }
            } else if (current == tail) { // 如果要删除的是尾节点
                tail = tail.prev;
                tail.next = null;
            } else { // 如果要删除的是中间节点
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
            size--; // 链表长度减少
            return;
        }
        current = current.next;
    }
}

删除所有值为key的节点

public void removeAllKey(int key) {
    Node current = head;
    while (current != null) { // 遍历链表
        if (current.data == key) {
            if (current == head) { // 如果要删除的是头节点
                head = head.next;
                if (head != null) {
                    head.prev = null;
                } else {
                    tail = null; // 如果链表只有一个节点
                }
            } else if (current == tail) { // 如果要删除的是尾节点
                tail = tail.prev;
                tail.next = null;
            } else { // 如果要删除的是中间节点
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
            size--; // 链表长度减少
        }
        current = current.next;
    }
}

得到单链表的长度

public int size() {
    return size;
}

显示链表内容

public void display() {
    Node current = head;
    while (current != null) { // 遍历链表
        System.out.print(current.data + " <-> ");
        current = current.next;
    }
    System.out.println("null"); // 链表末尾
}

清空链表

public void clear() {
    head = tail = null; // 将头节点和尾节点置为空
    size = 0;           // 链表长度重置为0
}

结果

public static void main(String[] args) {
    LinkedTest list = new LinkedTest();
    list.addLast(1);
    list.addLast(2);
    list.addLast(3);
    list.addFirst(0);
    list.addIndex(2, 5);
    list.display(); // 输出: 0 <-> 1 <-> 5 <-> 2 <-> 3 <-> null

    System.out.println("Contains 2: " + list.contains(2)); // 输出: true
    list.remove(2);
    list.display(); // 输出: 0 <-> 1 <-> 5 <-> 3 <-> null

    list.addLast(3);
    list.addLast(3);
    list.removeAllKey(3);
    list.display(); // 输出: 0 <-> 1 <-> 5 <-> null

    System.out.println("Size: " + list.size()); // 输出: 3
    list.clear();
    list.display(); // 输出: null
}

使用

构造方法

构造方法	说明
`LinkedList()`	这是一个无参构造方法，用于创建一个空的 `LinkedList` 实例。
`public LinkedList(Collection<? extends E> c)`	这是一个带参构造方法，接受一个集合 `c` 作为参数。它会使用集合 `c` 中的元素来构造一个新的 `LinkedList` 实例。集合 `c` 中的元素类型必须是 `LinkedList` 元素类型 `E` 或其子类型。

public static void main(String[] args) {
    // 使用无参构造方法创建一个空的LinkedList
    LinkedList<String> list1 = new LinkedList<>();
    list1.add("A");
    list1.add("B");
    System.out.println("list1: " + list1); // 输出: list1: [A, B]

    // 使用ArrayList作为集合容器
    Collection<String> collection = new ArrayList<>();
    collection.add("C");
    collection.add("D");

    // 使用带参构造方法创建LinkedList
    LinkedList<String> list2 = new LinkedList<>(collection);
    System.out.println("list2: " + list2); // 输出: list2: [C, D]
}

常用方法

方法	说明
boolean add(E e)	将元素 `e` 插入到列表的末尾。
void add(int index, E element)	将元素 `element` 插入到列表的指定 `index` 位置。
boolean addAll(Collection<? extends E> c)	将集合 `c` 中的所有元素插入到列表的末尾。
E remove(int index)	删除并返回列表中指定 `index` 位置的元素。
boolean remove(Object o)	删除列表中第一次出现的指定元素 `o`。
E get(int index)	返回列表中指定 `index` 位置的元素。
E set(int index, E element)	将列表中指定 `index` 位置的元素替换为 `element`，并返回原来的元素。
void clear()	清空列表中的所有元素。
boolean contains(Object o)	判断列表中是否包含指定元素 `o`。
int indexOf(Object o)	返回列表中第一个出现的指定元素 `o` 的索引，如果不存在则返回 `-1`。
int lastIndexOf(Object o)	返回列表中最后一个出现的指定元素 `o` 的索引，如果不存在则返回 `-1`。
List<E> subList(int fromIndex, int toIndex)	返回列表中从 `fromIndex`（包含）到 `toIndex`（不包含）之间的子列表。

使用

public static void main(String[] args) {
    List<String> list = new ArrayList<>();

    // 添加元素
    list.add("A"); // 尾插
    list.add(0, "B"); // 在索引0处插入
    System.out.println("After add: " + list); // 输出: [B, A]

    // 添加集合
    List<String> anotherList = new ArrayList<>();
    anotherList.add("C");
    anotherList.add("D");
    list.addAll(anotherList); // 尾插集合
    System.out.println("After addAll: " + list); // 输出: [B, A, C, D]

    // 删除元素
    list.remove(1); // 删除索引1的元素
    System.out.println("After remove by index: " + list); // 输出: [B, C, D]
    list.remove("C"); // 删除第一个出现的"C"
    System.out.println("After remove by object: " + list); // 输出: [B, D]

    // 获取和设置元素
    System.out.println("Element at index 1: " + list.get(1)); // 输出: D
    list.set(1, "E"); // 设置索引1的元素为"E"
    System.out.println("After set: " + list); // 输出: [B, E]

    // 判断是否包含元素
    System.out.println("Contains 'B': " + list.contains("B")); // 输出: true

    // 查找元素索引
    System.out.println("Index of 'E': " + list.indexOf("E")); // 输出: 1

    // 清空列表
    list.clear();
    System.out.println("After clear: " + list); // 输出: []

    // 子列表
    list.add("F");
    list.add("G");
    list.add("H");
    List<String> subList = list.subList(1, 3); // 获取子列表
    System.out.println("SubList: " + subList); // 输出: [G, H]
}

结果

遍历

有两种遍历,for循环遍历和使用迭代器遍历(正向+反向)

public static void main(String[] args) {
    List<String> list = new ArrayList<>();

    list.add("A");
    list.add("B");
    list.add("C");
    list.add("D");
    list.add("E");
    list.add("F");
    list.add("G");
    System.out.println(list);

    // for循环遍历
    for (int i = 0; i < list.size(); i++) {
        System.out.print(list.get(i)+" ");
    }
    System.out.println();

    // 使用迭代器遍历---正向遍历
    ListIterator<String> it = list.listIterator();
    while (it.hasNext()) {
        System.out.print(it.next() + " ");
    }
    System.out.println();

    // 使用反向迭代器---反向遍历
    ListIterator<String> rit = list.listIterator(list.size());
    while (rit.hasPrevious()) {
        System.out.print(rit.previous() + " ");
    }
    System.out.println();
}

ArrayList和LinkedList区别

特性	ArrayList	LinkedList
底层数据结构	动态数组	双向链表
内存占用	较少（仅存储数据和部分容量）	较多（每个节点需要存储前后指针）
随机访问性能	快（通过索引直接访问，时间复杂度 O(1)）	慢（需要遍历链表，时间复杂度 O(n)）
插入/删除性能	慢（需要移动元素，时间复杂度 O(n)）	快（只需修改指针，时间复杂度 O(1)）
头插/头删性能	慢（需要移动所有元素）	快（只需修改头节点指针）
尾插/尾删性能	快（直接操作尾部）	快（直接操作尾部）
中间插入/删除性能	慢（需要移动元素）	快（只需修改指针）
内存连续性	连续内存空间	非连续内存空间
适用场景	频繁随机访问、少量插入删除	频繁插入删除、少量随机访问
扩容机制	动态扩容（默认 1.5 倍）	无需扩容（动态添加节点）
空间浪费	可能存在（预留容量）	无（按需分配节点）
实现接口	实现 `List` 接口	实现 `List` 和 `Deque` 接口
线程安全	非线程安全	非线程安全

LinkedList和链表

链表

基础概念

结构示例

链表实现

构造节点

头插法

尾插法

任意位置插入

查找是否包含关键字key

删除第一次出现关键字为key的节点

删除所有值为key的节点

得到单链表的长度

清空链表

显示链表内容

输出结果

LinkedList

基本概念

模拟实现

构造节点

头插法

尾插法

任意位置插入

查找是否包含关键字key

删除第一次出现关键字为key的节点

删除所有值为key的节点

得到单链表的长度

显示链表内容

清空链表

结果

使用

构造方法

常用方法

使用

结果

遍历

ArrayList和LinkedList区别

网站公告

今日签到

热门文章

最新发布