目录

1.链表

2.链表的模拟实现

3.LinkedList的模拟实现

4.LinkedList的使用

4.1 什么是LinkedList

4.2 LinkedList的使用

5.ArrayList和LinkedList的区别

我的GitHub：Powerveil · GitHub

我的Gitee：Powercs12 (powercs12) - Gitee.com

皮卡丘每天学Java

1.链表

链表也是线性表的一种。

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

注意：

1. 从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续

2. 现实中的结点一般都是从堆上申请出来

3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环 

虽然有这么多的链表的结构，但是我们重点掌握两种:

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
• 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.链表的模拟实现

public class MyLinkedList {public ListNode head;static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}/*** 通过穷举的方式 创建一个链表出来* 现在这样做  只是为了能够让初学者对这个结构更好的了解* 后期 我会改回来。*/public void createList() {ListNode node1 = new ListNode(10);ListNode node2 = new ListNode(12);ListNode node3 = new ListNode(23);ListNode node4 = new ListNode(34);node1.next = node2;node2.next = node3;node3.next = node4;head = node1;}public void display() {ListNode cur = head;while (cur != null) {System.out.printf(cur.val + " ");cur = cur.next;}System.out.println();}public void display(ListNode node) {ListNode cur = node;while (cur != null) {System.out.printf(cur.val + " ");cur = cur.next;}System.out.println();}//查找是否包含关键字key是否在单链表中public boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) return true;cur = cur.next;}return false;}//得到单链表的长度public int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}//头插法:O(1)public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}//尾插法:O(n)public void addLast(int data) {ListNode node = new ListNode(data);if (head == null) {head = node;} else {ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}}private void checkIndex(int index) {if (index < 0 || index > size()) {throw new IndexNotLegalException("index的值不合法");}}//任意位置插入，第一个数据节点0号下标public void addIndex(int index, int data) {checkIndex(index);//下标为0是头插if (index == 0) {addFirst(data);}//下标为size是尾插if (index == size()) {addLast(data);}//中间插ListNode node = new ListNode(data);ListNode cur = findIndex(index - 1);node.next = cur.next;cur.next = node;}//找到指定下标节点public ListNode findIndex(int index) {ListNode cur = head;while (index > 0) {cur = cur.next;index--;}return cur;}//删除第一次出现关键字为key的节点public void remove(int key) {
//        if (head == null) {
//            throw new RuntimeException("链表没有元素不可以删除");
//        }if (head.val == key) {head = head.next;return;}ListNode cur = searchPrevOfKey(key);if (cur == null) return;ListNode del = cur.next;cur.next = del.next;
//        cur.next = cur.next.next;}//根据值找到前一个节点private ListNode searchPrevOfKey(int key) {if (head == null) return null;ListNode cur = head;while (cur.next != null) {if (cur.next.val == key) return cur;cur = cur.next;}return null;}//删除所有值为key的节点public void removeAllKey(int key) {if (head == null) return;ListNode cur = head;while (cur.next != null) {ListNode curNext = cur.next;if (curNext.val == key) {cur.next = curNext.next;} else {cur = curNext;}}if (head.val == key) {head = head.next;}}//清空链表public void clear() {ListNode cur = head;while (cur != null) {ListNode curNext = cur.next;cur.next = null;cur = curNext;}head = null;}}

3.LinkedList的模拟实现

public class MyLinkedList {// 头节点public ListNode head;// 节点static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}// 打印链表public void display() {ListNode cur = head;while (cur != null) {System.out.printf(cur.val + " ");cur = cur.next;}System.out.println();}// 从某个节点开始打印public void display(ListNode node) {ListNode cur = node;while (cur != null) {System.out.printf(cur.val + " ");cur = cur.next;}System.out.println();}// 查找是否包含关键字key是否在单链表中public boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) return true;cur = cur.next;}return false;}// 得到单链表的长度public int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}// 头插法:O(1)public void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}// 尾插法:O(n)public void addLast(int data) {ListNode node = new ListNode(data);if (head == null) {head = node;} else {ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}}// 检查下标是否合法private void checkIndex(int index) {if (index < 0 || index > size()) {throw new IndexNotLegalException("index的值不合法");}}// 任意位置插入，第一个数据节点0号下标public void addIndex(int index, int data) {checkIndex(index);// 下标为0是头插if (index == 0) {addFirst(data);}// 标为size是尾插if (index == size()) {addLast(data);}// 中间插ListNode node = new ListNode(data);ListNode cur = findIndex(index - 1);node.next = cur.next;cur.next = node;}// 找到指定下标节点public ListNode findIndex(int index) {ListNode cur = head;while (index > 0) {cur = cur.next;index--;}return cur;}// 删除第一次出现关键字为key的节点public void remove(int key) {
//        if (head == null) {
//            throw new RuntimeException("链表没有元素不可以删除");
//        }if (head.val == key) {head = head.next;return;}ListNode cur = searchPrevOfKey(key);if (cur == null) return;ListNode del = cur.next;cur.next = del.next;
//        cur.next = cur.next.next;}// 根据值找到前一个节点private ListNode searchPrevOfKey(int key) {if (head == null) return null;ListNode cur = head;while (cur.next != null) {if (cur.next.val == key) return cur;cur = cur.next;}return null;}// 删除所有值为key的节点public void removeAllKey(int key) {if (head == null) return;ListNode cur = head;while (cur.next != null) {ListNode curNext = cur.next;if (curNext.val == key) {cur.next = curNext.next;} else {cur = curNext;}}if (head.val == key) {head = head.next;}}// 清空链表public void clear() {ListNode cur = head;while (cur != null) {ListNode curNext = cur.next;cur.next = null;cur = curNext;}head = null;}
}

4.LinkedList的使用

4.1 什么是LinkedList

官方文档

LinkedList (Java Platform SE 8 )

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

 下面是类图

1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问

注意：插入和删除的时间复杂度都为O(n)，因为找到节点需要遍历。

4.2 LinkedList的使用

LinkedList的构造

@SuppressWarnings({"all"})
public class Test {public static void main(String[] args) {// 构造一个空的LinkedListLinkedList linkedList1 = new LinkedList<>();List list = new ArrayList<>();list.add("Hello world!");list.add("每天学Java");list.add("逐渐提升");list.add("...");// 使用ArrayList构造LinkedListLinkedList linkedList2 = new LinkedList<>(list);}
}

LinkedList的其他常用方法介绍

    public static void main(String[] args) {LinkedList list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());System.out.println(list);// 在起始位置插入0list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()list.removeFirst(); // removeFirst(): 删除第一个元素list.removeLast(); // removeLast(): 删除最后元素list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回falseif (!list.contains(1)) {list.add(0, 1);}list.add(1);System.out.println(list);System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置int elem = list.get(0); // get(index): 获取指定位置元素list.set(0, 100); // set(index, elem): 将index位置的元素设置为elemSystem.out.println(list);// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回List copy = list.subList(0, 3);System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());}

LinkedList的遍历

    public static void main(String[] args) {LinkedList list = new LinkedList<>();list.add(1); // add(elem): 表示尾插list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);System.out.println(list.size());// foreach遍历for (int e:list) {System.out.print(e + " ");}System.out.println();// 使用迭代器遍历---正向遍历ListIterator it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();// 使用反向迭代器---反向遍历ListIterator rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();}

5.ArrayList和LinkedList的区别