数据结构（Java）——链表

1.概念及结构

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

2.分类

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

（1）单向或者双向

（2）带头或者不带头

（3）循环或者不循环

即单向带头循环链表、单向不带头循环链表、单向带头不循环链表、单向不带头不循环链表、双向带头循环链表、双向不带头循环链表、双向带头不循环链表和双向不带头不循环链表。

虽然有这么多的链表的结构，但是我们本篇主要讲两种 :

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

3. 代码实现

3.1 无头单向非循环链表

3.1.1 节点结构

static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}

3.1.2 方法接口

public interface ISingleLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key)
//得到单链表的长度
public int size()
//清空链表
public void clear() 
//打印链表
public void display()
}

3.1.3 功能实现

public class MySingleLinkedList implements IMySingleLinkedList {@Overridepublic void addFirst(int data) {ListNode node = new ListNode(data);node.next = head;head = node;}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {head = node;return;}ListNode cur = head;while (cur.next != null) {cur = cur.next;}cur.next = node;}@Overridepublic void addIndex(int index,int data) {//1.判断index的合法性try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}//2.index == 0  || index == size()if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//3. 找到index的前一个位置ListNode cur = findIndexSubOne(index);//4. 进行连接ListNode node = new ListNode(val);node.next = cur.next;cur.next = node;}private ListNode findIndexSubOne(int index) {int count = 0;ListNode cur = head;while (count != index-1) {cur = cur.next;count++;}return cur;}private void checkIndex(int index) throws IndexNotLegalException{if(index < 0 || index > size()) {throw new IndexNotLegalException("index不合法");}}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {if(head == null) {return;}if(head.val == key) {head = head.next;return;}ListNode cur = head;while (cur.next != null) {if(cur.next.val == key) {ListNode del = cur.next;cur.next = del.next;return;}cur = cur.next;}}@Overridepublic void removeAllKey(int key) {//1. 判空if(this.head == null) {return;}//2. 定义prev 和 curListNode prev = head;ListNode cur = head.next;//3.开始判断并且删除while(cur != null) {if(cur.val == key) {prev.next = cur.next;}else {prev = cur;}cur = cur.next;}//4.处理头节点if(head.val == key) {head = head.next;}}@Overridepublic int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void clear() {//head = null;ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.next = null;cur = curN;}head = null;}@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}
}//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}

3.2 无头双向非循环链表

3.2.1 节点结构

class ListNode {public int val;public ListNode prev;//前驱public ListNode next;//后继public ListNode(int val) {this.val = val;}}

3.2.2 方法接口

public interface IMyLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key);
//删除第一次出现关键字为key的节点
public void remove(int key);
//删除所有值为key的节点
public void removeAllKey(int key);
//得到单链表的长度
public int size();
public void display();
public void clear();
}

3.2.3 功能实现

public class MyLinkedList implements IMyLinkedList {public ListNode head;//标志头节点public ListNode last;//标志尾结点//头插法@Overridepublic void addFirst(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {node.next = head;head.prev = node;head = node;}}//尾插法@Overridepublic void addLast(int data){ListNode node = new ListNode(data);if(head == null) {//是不是第一次插入节点head = last = node;}else {last.next = node;node.prev = last;last = last.next;}}//任意位置插入,第一个数据节点为0号下标@Overridepublic void addIndex(int index,int data){try {checkIndex(index);}catch (IndexNotLegalException e) {e.printStackTrace();}if(index == 0) {addFirst(data);return;}if(index == size()) {addLast(data);return;}//1. 找到index位置ListNode cur = findIndex(index);ListNode node = new ListNode(data);//2、开始绑定节点node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}private void checkIndex(int index) {if(index < 0 || index > size()) {throw new IndexNotLegalException("双向链表插入index位置不合法: "+index);}}//查找是否包含关键字key是否在单链表当中@Overridepublic boolean contains(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点@Overridepublic void remove(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删除 处理头节点if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}return;//删完一个就走}cur = cur.next;}}//删除所有值为key的节点@Overridepublic void removeAllKey(int key){ListNode cur = head;while (cur != null) {if(cur.val == key) {//开始删除 处理头节点if(cur == head) {head = head.next;if(head != null) {head.prev = null;}else {//head == null 证明只有1个节点last = null;}}else {cur.prev.next = cur.next;if(cur.next == null) {//处理尾巴节点last = last.prev;}else {cur.next.prev = cur.prev;}}}cur = cur.next;}}//得到双向链表的长度@Overridepublic int size(){int count = 0;ListNode cur = head;while (cur != null) {count++;cur = cur.next;}return count;}@Overridepublic void display(){ListNode cur = head;while (cur != null) {System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}@Overridepublic void clear(){ListNode cur = head;while (cur != null) {ListNode curN = cur.next;//cur.val = null;cur.prev = null;cur.next = null;cur = curN;}head = last = null;}
}
//自定义异常类
public class IndexNotLegalException extends RuntimeException{public IndexNotLegalException() {}public IndexNotLegalException(String msg) {super(msg);}
}

4.LinkedList

4.1 概念

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

注意：

1. LinkedList 实现了 List 接口

2. LinkedList 的底层使用了双向链表

3. LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问

4. LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为 O(1)

5. LinkedList 比较适合任意位置插入的场景

4.2 使用

4.2.1 构造方法

方法	说明
LinkedList()	无参构造
public LinkedList(Collection<? extends E> c)	使用其他集合容器中元素构造List

代码示例：

public static void main(String[] args) {// 构造一个空的LinkedListList<String> list1 = new LinkedList<>();list1.add("sas");list1.add("asd");list1.add("Jsd");System.out.print("list1: ");for(int i = 0; i < list1.size();i++){System.out.print(list1.get(i)+" ");}System.out.println();System.out.print("list2: ");List<String> list2 = new LinkedList<>(list1);for(int i = 0; i < list2.size();i++){System.out.print(list2.get(i)+" ");}}

运行结果如下：

4.2.2 其他常用方法

方法	解释
boolean add( E e)	尾插 e
void add(int index, E element)	将 e 插入到 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 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List<E> subList(int fromIndex, int toIndex)	截取部分list

代码示例：

public static void main(String[] args) {LinkedList<Integer> 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<Integer> copy = list.subList(0, 3);System.out.println(list);System.out.println(copy);list.clear(); // 将list中元素清空System.out.println(list.size());
}

运行结果如下：

4.3 遍历

我们之前常用的遍历方式有for循环、foreach循环和while循环等来进行遍历，LinkedList除了使用这些外， 还可以使用迭代器进行遍历。

代码示例：

public static void main(String[] args) {LinkedList<Integer> 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);// 使用迭代器遍历---正向遍历ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();
// 使用反向迭代器---反向遍历ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();
}

运行结果如下：

5.ArrayList和LinkedList的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
头插	需要搬移元素，效率低 O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁

本文是作者学习后的总结，如果有什么不恰当的地方，欢迎大佬指正！！！