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

★引言：

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

一. 单向链表

（一）属性

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;}@Overridepublic 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)
逻辑与空间上都连续	逻辑上连续，空间上不连续
浪费空间严重	不会浪费空间
适用于频繁访问	适用于频繁插入与删除