数据结构3-单双链表的泛型实现及ArrayList与LinkedList的区别

发布于：2025-07-26 ⋅ 阅读:(20) ⋅ 点赞:(0)

文章目录

★引言：

本篇博客依旧是基于泛型实现的简易单双链表，最后都会测试其中的方法，如果这篇博客对你有所帮助，可以给个三连，小编都会回关的！

一. 单向链表

（一）属性

  1. 单链表中每个节点 Node 有两个域，值域 val，连接下一节点的域 next
  2. 将一个个节点定义为静态内部类，同时单链表让头结点 head 指向第一个节点

在这里插入图片描述

public class MySingleLinkedList<T> {
    public Node head;

    static class Node {
        public Object val;
        public Node next;

        public Node(Object val, Node next) {
            this.val = val;
            this.next = next;
        }

        public Node() {
        }

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

}

（二）方法实现

（1）addFirst(T data)

  1. 头插法
  2. 有两种情况：
    ① 头节点为 null，将头节点 head 直接指向 node
    ② 头节点不为 null，将该节点 node 与链表连接起来，head 节点指向 node

在这里插入图片描述

    //头插法
    public void addFirst(T data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
        }else {
            node.next = head;
            head =  node;
        }
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addFirst(12);
        list.addFirst(23);
        list.addFirst(34);
        list.addFirst(45);
        list.display();

        MySingleLinkedList<String> list1 = new MySingleLinkedList<>();
        list1.addFirst("hello");
        list1.addFirst("my");
        list1.addFirst("name");
        list1.addFirst("is");
        list1.addFirst("Ran");
        list1.display();
    }

在这里插入图片描述

（2）addLast(T data)

  1. 尾插法
  2. 有两种情况：
    ① 头节点为 null，将头节点 head 直接指向 node
    ② 头节点不为 null，找到最后一个节点 cur，将该节点 cur 与 node 连接起来

在这里插入图片描述

    //尾插法
    public void addLast(T data) {
        Node node = new Node(data);
        if (head == null) {
            head = node;
            return;
        }
        Node cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.display();

        MySingleLinkedList<String> list1 = new MySingleLinkedList<>();
        list1.addLast("hello");
        list1.addLast("my");
        list1.addLast("name");
        list1.addLast("is");
        list1.addLast("Ran");
        list1.display();
    }

在这里插入图片描述

（3）dispaly()

  1. 打印链表元素
  2. 从头结点 head遍历完所有系欸但，打印其中元素
    public void display() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

（4）size()

  1. 得到单链表的⻓度
  2. 变量单链表，来求长度
    //得到单链表的⻓度
    public int size() {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.display();
        System.out.println("链表长度：" + list.size());
    }

在这里插入图片描述

（5）IllegalIndexExc

下标不合法异常

public class IllegalIndexExc extends RuntimeException{
    public IllegalIndexExc() {

    }

    public IllegalIndexExc(String message) {
        super(message);
    }
}

（6）addIndex(int index, T data)

  1. 任意位置插⼊,第⼀个数据节点为0号下标
  2. 先判断下标是否合法，合法后可以插入，不合法抛异常
    //任意位置插⼊,第⼀个数据节点为0号下标
    public void addIndex(int index, T data) {
        int size = size();
        if (index < 0 || index > size) {
            throw new IllegalIndexExc("index 不合法！！！");
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size) {
            addLast(data);
            return;
        }
        Node<T> node = new Node<T>(data);
        Node<T> cur = head;
        while (index - 1 > 0) {
            cur = cur.next;
            index--;
        }
        node.next = cur.next;
        cur.next = node;
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        System.out.print("插入前：");
        list.display();
        System.out.println("链表长度：" + list.size());
        list.addIndex(2,56);
        System.out.print("插入后：");
        list.display();
        System.out.println("链表长度：" + list.size());
    }

在这里插入图片描述

（7）contains(Object key)

  1. 查找是否包含关键字key是否在单链表当中
  2. 遍历链表查找
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(Object key) {
        Node<T> cur = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        System.out.print("插入前：");
        list.display();
        System.out.println("链表长度：" + list.size());
        list.addIndex(2,56);
        System.out.print("插入后：");
        list.display();
        System.out.println("链表长度：" + list.size());
        System.out.println("是否存在：" + list.contains(56));
        System.out.println("是否存在：" + list.contains(66));
    }

在这里插入图片描述

（8）remove(Object key)

  1. 删除第⼀次出现关键字为key的节点
  2. 先判断是否存在这个值
  3. 遍历找到第一个跳出循环 找出节点 cur，两种情况：
    ① 该节点是 head，头节点向右移，同时 head 节点置为 null
    ② 不是头节点，要设立前驱节点prev与目标节点cur

在这里插入图片描述

    //删除第⼀次出现关键字为key的节点
    public void remove(Object key) {
        if (!contains(key)) {
            System.out.println("不存在该节点！！！");
            return;
        }
        Node<T> cur = head;
        Node<T> prev = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                break;
            }
            prev = cur;
            cur = cur.next;
        }
        if (cur == head) {
            head = head.next;
            return;
        }
        prev.next = cur.next;
        cur.next = null;
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addLast(12);
        list.addLast(22);
        list.display();
        System.out.println("链表长度：" + list.size());
        list.remove(22);
        list.display();
        System.out.println("链表长度：" + list.size());
    }

在这里插入图片描述

（9）removeAllKey(Object key)

  1. 删除所有值为key的节点
  2. 需要前驱 prev 与目标节点 cur，让 prev 与 cur 连接，最后判断 head 节点是否是目标值

在这里插入图片描述

    //删除所有值为key的节点
    public void removeAllKey(Object key) {
        if (!contains(key)) {
            System.out.println("没有你要删除的节点!!!");
            return;
        }
        Node<T> cur = head;
        Node<T> prev = head;
        while (cur != null) {
            if (cur.val.equals(key)) {
                prev.next = cur;
                prev = cur;
                prev.next = null;
            }
            cur = cur.next;
        }
        if (head.val.equals(key)) {
            head = head.next;
        }
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addLast(12);
        list.addLast(12);
        list.display();
        System.out.println("删除前链表长度：" + list.size());
        list.removeAllKey(12);
        list.display();
        System.out.println("删除后链表长度：" + list.size());
    }

在这里插入图片描述

（10）clear()

删除所有值

    public void clear() {
        Node<T> cur = head;
        head = null;
        while (cur != null) {
            Node<T> curN = cur.next;
            cur.next = null;
            cur = curN;
        }
    }
测试：
    public static void main(String[] args) {
        MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.display();
        System.out.println("删除前链表长度：" + list.size());
        list.clear();
        list.display();
        System.out.println("删除后链表长度：" + list.size());
    }

在这里插入图片描述

二. 双向链表

（一）属性

  1. 双向链表中每个节点 Node 有三个域，值域 key，连接下一节点的域 next，连接上一节点的域 prev
  2. 将一个个节点定义为静态内部类，同时双向链表让头结点 head 指向第一个节点 ，尾节点 last 指向最后一个节点
import java.util.Objects;

public class MyLinkedList<E> {
    static class Node<E> {
        public E key;
        public Node<E> prev;
        public Node<E> next;

        public Node() {
        }

        public Node(E key) {
            this.key = key;
        }

        @Override
        public boolean equals(Object o) {
            if (o == null || getClass() != o.getClass()) return false;
            Node<?> node = (Node<?>) o;
            return Objects.equals(key, node.key) && Objects.equals(prev, node.prev) && Objects.equals(next, node.next);
        }
    }
}

（二）方法实现

（1）addFirst(E data)

  1. 头插法
  2. 两种情况：
    ① head = last = null，那么让头与尾都指向 node
    ② 头尾不为空，改变 head 的前驱 prev 与 node 的后置 next

在这里插入图片描述

    //头插法
    public void addFirst(E data) {
        Node<E> node = new Node<>(data);
        if (head == null && last == null) {
            head = last = node;
            return;
        }
        node.next = head;
        head.prev = node;
        head = head.prev;
    }
测试：
    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addFirst(12);
        list.addFirst(23);
        list.addFirst(34);
        list.addFirst(45);
        System.out.print("头插法：");
        list.display();
    }

在这里插入图片描述

（2）addLast(E data)

  1. 尾插法
  2. 两种情况：
    ① head = last = null，那么让头与尾都指向 node
    ② 头尾不为空，改变 last 的后驱 next 与 node 的前驱 prev

在这里插入图片描述

   //尾插法
    public void addLast(E data) {
        Node<E> node = new Node<>(data);
        if (head == null && last == null) {
            head = last = node;
            return;
        }
        last.next = node;
        node.prev = last;
        last = last.next;
    }
测试：
    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        System.out.print("尾插法：");
        list.display();
    }

在这里插入图片描述

（3）display()

遍历链表，打印所有元素

    public void display() {
        Node<E> cur = head;
        while (cur != null) {
            System.out.print(cur.key + " ");
            cur = cur.next;
        }
        System.out.println();
    }

（4）size()

求链表长度

    //得到单链表的⻓度
    public int size() {
        int count = 0;
        Node<E> cur = head;
        while (cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
测试：

在这里插入图片描述

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        System.out.print("尾插法：");
        list.display();
        System.out.println("链表长度：" + list.size());
    }

（5）addIndex(int index, E data)

  1. 任意位置插⼊,第⼀个数据节点为0号下标
  2. 判断下标是否合法
  3. 分为头插，尾插，中间插

在这里插入图片描述

    //任意位置插⼊,第⼀个数据节点为0号下标
    public void addIndex(int index, E data) {
        int size = size();
        if (index < 0 || index > size) {
            throw new IllegalIndexExc("index 不合法！！！");
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size) {
            addLast(data);
            return;
        }
        Node<E> node = new Node<>(data);
        Node<E> cur = head;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        cur.prev.next = node;
        node.prev = cur.prev;
        node.next = cur;
        cur.prev = node;
    }
测试：

在这里插入图片描述

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        System.out.print("插入前：");
        list.display();
        System.out.println("链表长度：" + list.size());
        list.addIndex(2,56);
        System.out.print("插入后：");
        list.display();
        System.out.println("链表长度：" + list.size());
    }

（6）contains(Object key)

链表中是否含有该值，遍历链表

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(Object key) {
        Node<E> cur = head;
        while (cur != null) {
            if (cur.key.equals(key)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
测试：

在这里插入图片描述

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addIndex(2,56);
        System.out.println("45 是否存在：" + list.contains(45));
        System.out.println("66 是否存在：" + list.contains(66));
    }

（7）remove(Object key)

  1. 删除第⼀次出现关键字为key的节点
  2. 四种情况：
    ① 目标节点 cur 既是 head 也是 last
    ② 目标节点 cur 是 head 但不是 last
    ③ 目标节点 cur 不是 head 是 last
    ④ 目标节点 cur 既不是 head 也不是 last
    四种情况都要讨论

在这里插入图片描述

    //删除第⼀次出现关键字为key的节点
    public void remove(Object key) {
        if (!contains(key)) {
            System.out.println("没有该值你不能删除！！！");
            return;
        }
        Node<E> cur = head;
        while (cur != null) {
            if (cur.key.equals(key)) {
                if (cur == head && cur == last) {
                    head = last = null;
                }else if (cur == head) {
                    cur.next.prev = cur.prev;
                    head = head.next;
                }else if (cur == last) {
                    cur.prev.next = cur.next;
                    last = last.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
                return;
            }
            cur = cur.next;
        }
    }
测试：

在这里插入图片描述

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addIndex(2,56);
        list.display();
        System.out.print("删除12：");
        list.remove(12);
        list.display();
        System.out.print("删除56：");
        list.remove(56);
        list.display();
        System.out.print("删除45：");
        list.remove(45);
        list.display();
    }

（8）removeAllKey(Object key)

  1. 删除所有值为key的节点
  2. 同分四种情况，跟上面的remove方法一致，这里不过多赘述，直接将return删去，就是该方法
    //删除所有值为key的节点
    public void removeAllKey(Object key) {
        if (!contains(key)) {
            System.out.println("没有该值你不能删除！！！");
            return;
        }
        Node<E> cur = head;
        while (cur != null) {
            if (cur.key.equals(key)) {
                if (cur == head && cur == last) {
                    head = last = null;
                }else if (cur == head) {
                    cur.next.prev = cur.prev;
                    head = head.next;
                }else if (cur == last) {
                    cur.prev.next = cur.next;
                    last = last.prev;
                }else {
                    cur.prev.next = cur.next;
                    cur.next.prev = cur.prev;
                }
            }
            cur = cur.next;
        }
    }
测试：

在这里插入图片描述

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(12);
        list.addLast(13);
        list.addLast(12);
        System.out.print("删除前：");
        list.display();
        list.removeAllKey(12);
        System.out.print("删除后：");
        list.display();
    }

（9）clear()

清除链表

    public void clear() {
        Node<E> cur = head;
        while (cur != null) {
            Node<E> curN = cur.next;
            cur.next = null;
            cur.prev = null;
            cur = curN;
        }
        head = null;
        last = null;
    }
测试：

在这里插入图片描述

    public static void main(String[] args) {
        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addLast(12);
        list.addLast(13);
        list.addLast(12);
        System.out.print("删除前：");
        list.display();
        list.clear();
        System.out.print("删除后：");
        list.display();
    }

三. ArrayList与LinkedList的区别

ArrayList LinkedList
尾插插入时间复杂度O(1)，头插时间复杂度O(N) 头插尾插都是O(1)
删除元素时间复杂度O(N) 删除元素时间复杂度O(1)
支持随机访问，随机访问时间复杂度(1) 不支持随机访问，随机访问时间复杂度(N)
逻辑与空间上都连续 逻辑上连续，空间上不连续
浪费空间严重 不会浪费空间
适用于频繁访问 适用于频繁插入与删除

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布