?【引言】
- 上篇文章我们介绍了ArrayList的使用以及它的一些相关知识，还模拟实现了简单的顺序表
- 我们在这个过程中，有了以下的思考：ArrayList的底层是使用数组来存储元素的
- 这就导致当ArrayList的任意位置插入或删除元素时，就需要将后续元素整体向后移或者向前移，所以时间复杂度为O(N)
- 因此ArrayList不适合做任意位置插入和删除比较多的场景
- 所以，Java集合中又引入了LinkedList，即链表结构
目录
?
1.链表
1.1链表的概念和结构
? ? ? ? ? ?链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的
?
?实际中链表的结构非常多样，有单向和双向、带头和不带头、循环和非循环
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环
以上情况组合起来，就有8种链表结构
下面我们看一张图
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。这种结构在笔试面试中出现很多。
?
另一个用得较多的是无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表
?
下面我们介绍一下链表是如何实现的
首先简要介绍一下节点的概念
?如图便是一个简单的节点的示意图，它有两个域：数值域和next域
?1.2单向非循环链表实现
我们要实现哪些功能呢？
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public boolean 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();先看一下整体的代码??
package listdemo;
public class MySingleList {
//节点是链表的一个组成部分，一般情况下把节点作为内部类
static class ListNode{
public int val;//数值域
public ListNode next;//存储下一个节点的地址
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//代表单链表的头节点的引用
/**
* 这里只是简单的进行链表的构造
*/
public void createList(){
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
public void display() {
ListNode cur = head;
while(cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
/**
*头插法
* @param data
*/
public void addFirst(int data){
ListNode node = new ListNode(data);
if(this.head == null){
this.head =node;
}else{
node.next = this.head;
this.head = node;
}
/*可以直接这样写
node.next = this.head;
this.head = node;*/
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(this.head == null){
this.head = node;
}else{
ListNode cur = head;
while(cur.next != null){
cur = cur.next;
}
//cur.next==null时
cur.next = node;
}
}
private void checkIndexAdd(int index){
if(index<0 || index>size()){
throw new MySingleListIndexOutOfException("任意插入位置的时候index不合法");
}
}
/**
* 找到index位置的前一个位置处的节点
* @param index
* @return 该节点的地址
*/
private ListNode findIndexSubOne(int index){
ListNode cur = this.head;
int count = index-1;
while(count!=0){
cur = cur.next;
count--;
}
return cur;
}
/**
* 任意位置插入,第一个数据节点为0号下标
* @param index
* @param data
*/
public void addIndex(int index,int data) throws MySingleListIndexOutOfException {
checkIndexAdd(index);
if(index == 0){
addFirst(data);//头插法
return ;
}
if(index == size()){
addLast(data);//尾插法
return;
}
ListNode node = new ListNode(data);
ListNode cur = findIndexSubOne(index);//找到index位置的前一个节点，记为cur
//插入
node.next = cur.next;
cur.next = node;
}
//查找是否包含关键字key在单链表当中
public boolean contains(int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
/**
* 删除第一次出现关键字为key的节点
* @param key
*/
public void remove(int key){
if(this.head == null){
System.out.println("此时链表为空，不能进行删除");
return ;
}
if(this.head.val == key){//判断第一个节点是不是我要删除的节点
this.head = this.head.next;
return ;
}
ListNode cur = this.head;
while(cur.next != null){
if(cur.next.val == key){
//进行删除
ListNode del = cur.next;
cur.next = del.next;
return ;
}
cur = cur.next;
}
}
/**
* 删除所有值为key的节点
* 1.要求时间复杂度为 O(N)
* 2.要求只遍历单链表一遍
* @param key
*/
public void removeAllKey(int key){
//先判断 head 是否为空
if(this.head == null){
return ;
}
ListNode cur = this.head.next;
ListNode prev = this.head;
while(cur != null){
if(cur.val == key){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
//单独处理头节点问题
if(this.head.val == key){
this.head = head.next;
}
}
//得到单链表的长度
public int size(){
int count = 0;
ListNode cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
/**
* 清空链表所有内容
* 当我们调用clear函数的时候，会将这个链表当中的所有的节点回收
*/
public void clear(){
//做法一，简单粗暴
//this.head = null;
//做法二，一个一个删除
ListNode cur = this.head;
ListNode curNext = null;
while(cur != null){
curNext = cur.next;
cur.next = null;
cur = curNext;
}
head = null;
}
}
单向非循环链表实现过程的分析?
1.创建链表
注意：这只是简单意义上的创建链表?
?2.如何遍历链表
3.头插
4.尾插
?5.任意位置插入
6.删除?
一些问题
测试：
7.删除所有值为key的节点?
我们的要求是：
1.时间复杂度为 O(N)
2.最多遍历单链表一遍
首先我们需要清楚，这个删除的核心是：要找到需要删除的节点的上一个节点?
?由于在一开始就处理头节点就需要删除的特殊情况比较困难，所以我们最后再处理
? 注：如果我们一开始就处理头节点的问题，那么我们需要用循环语句，直到头节点的值不等于key循环才停止，但是如果我们最后再处理头节点的问题，只需要一个 if 语句判断一下即可?
2.LinkedList的模拟实现
LinkedList底层就是一个双向链表，我们来实现一个双向链表。
首先看一下它有哪些方法
// 2、无头双向链表实现
public class MyLinkedList {
//头插法
public void addFirst(int data);
//尾插法
public void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
public boolean 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();
}?下面我们来模拟实现一下
package LinkedListDemo;
public class MyLinkedList {
static class ListNode {
public int val;
public ListNode prev;//前驱
public ListNode next;//后继
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;//标记头部
public ListNode last;//标记尾部
//头插法
public void addFirst(int data){
ListNode node = new ListNode(data);
if(head == null){
head = node;
last = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
}
//尾插法
public void addLast(int data){
ListNode node = new ListNode(data);
if(head == null){
head = node;
last = node;
}else{
last.next = node;
node.prev = last;
last = node;
}
}
private ListNode searchIndex(int index){
ListNode cur = head;
while(index != 0){
cur = cur.next;
index--;
}
return cur;
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
if(index < 0 || index > size()) {
System.out.println("index不合法");
}
if(index == 0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return;
}
ListNode cur = searchIndex(index);
//此时cur拿到了index下标的节点的地址
ListNode node = new ListNode(data);
node.next = cur;
node.prev = cur.prev;
cur.prev.next = node;
cur.prev = node;
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
ListNode cur = head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
ListNode cur = head;
while(cur != null){
if (cur.val == key) {
if(cur == head){
head = head.next;
head.prev = null;
}else{
//中间和尾巴的情况
cur.prev.next = cur.next;
if(cur.next != null) {
//cur不是尾节点
cur.next.prev = cur.prev;
}else{
last = last.prev;
}
}
return;
}else{
cur = cur.next;
}
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
ListNode cur = head;
while(cur != null){
if (cur.val == key) {
if(cur == head){
head = head.next;
head.prev = null;
}else{
//中间和尾巴的情况
cur.prev.next = cur.next;
if(cur.next != null) {
//cur不是尾节点
cur.next.prev = cur.prev;
}else{
last = last.prev;
}
}
cur = cur.next;
}else{
cur = cur.next;
}
}
}
//得到单链表的长度
public int size(){
int count = 0;
ListNode cur = head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
/**
* 打印
*/
public void display(){
ListNode cur = head;
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
}
/**
* 清空链表的内容
*/
public void clear(){
ListNode cur = head;
while(cur != null){
ListNode curNext = cur.next;
cur.prev = null;
cur.next = null;
cur = curNext;
}
//最后别忘了把 head 和 last 也置为空
head = null;
last = null;
}
}
3.LinkedList的使用
3.1LinkedList的简单介绍?
? LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后是通过引用将节点连接起来的，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
?
?这是LinkedList的部分源码
下面我们通过一张图加深一下对LinkedList的了解吧?
LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
?
在集合框架中，LinkedList也实现了List接口
3.2LinkedList的使用?
1.LinkedList的构造?
| 方法 | 解释 |
| LinkedList() | 无参构造 |
| public LinkedList(Collection<? extends E> c) | 使用其他集合容器中元素构造List |
我们看一个例子
public static void main(String[] args) {
// 构造一个空的LinkedList
List<Integer> list1 = new LinkedList<>();
List<String> list2 = new java.util.ArrayList<>();
list2.add("JavaSE");
list2.add("JavaWeb");
list2.add("JavaEE");
// 使用ArrayList构造LinkedList
List<String> list3 = new LinkedList<>(list2);
}2.LinkedList的一些常用方法
| 方法 | 解释 |
| 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 |
几个注意事项：
add
?我们通过源码可以知道，add默认是用的尾插
3.LinkedList的遍历
我们以 LinkedList里放的是Int类型为例
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
//for-each 遍历
for (int x:linkedList) {
System.out.print(x+" ");
}
System.out.println();
System.out.println("=================");
//使用迭代器遍历 1
Iterator<Integer> it = linkedList.iterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
// it.next() 不仅会打印下一个 还会让it向后走一步
}
System.out.println();
System.out.println("==================");
//使用迭代器遍历 2
ListIterator<Integer> listIterator = linkedList.listIterator();
while (listIterator.hasNext()){
System.out.print(listIterator.next()+" ");
}
System.out.println();
System.out.println("===================");;
//使用迭代器遍历（反向遍历）
ListIterator<Integer> listIterator1 = linkedList.listIterator(linkedList.size());
while(listIterator1.hasPrevious()){
System.out.print(listIterator1.previous()+" ");
}
System.out.println();
}4.LinkedList和ArrayList的区别
| 不同点 | ArrayList | LinkedList |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 头插 | 需要搬移元素，效率低O(N) | 只需修改引用的指向，时间复杂度为O(1) |
| 插入 | 空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
我们简单来概括下：
1.存储方式上的不同：
ArrayList? 是一块连续的内存，物理上和逻辑上都连续
LinkedList? 物理上不一定连续，逻辑上是连续的
2.增删查改的区别
增加元素、删除元素比较频繁时，建议使用LinkedList，只需要修改指向就可以
如果要频繁地查找下标、修改，建议使用ArrayList
?
?
? ??
