LinkedList和链表(下)

1. 什么是LinkedList

在练习了单链表的自我实现和单链表的一些习题之后,我们正式来认识一下java提供的LinkedList,这是一种双向链表结构,在增删元素的时候效率比较高,不需要像ArrayList一样搬运元素.但是在查找方面效率比较低(需要遍历链表),ArrayList效率就比较高(直接由数组下标访问).

我们来看一下它底层接口实现

从上图我们可以看出

1. LinkedList实现了List接口

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

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

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

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

2. 实现一个自己的双向链表

为了更好的了解双向链表LinkedList,我们自己来实现一个.

先来认识一下Ilist接口,一下是它的抽象方法.

然后我们写一个MyLinkedList实现依次实现Ilist接口,然后后续我们依次重写每一个方法.在此之前我们先把结点内部类先构造好,链表是一个大的整体,而结点是其中的小整体,因此我们就用内部类来表示结点.每个结点的属性是由val,next,prev组成,val里面放置的是我们结点的值,next放置的是下一个结点的地址,prev放置的是上一个结点的地址.然后我们提供一个构造方法,每次创建一个结点的适合我们就需要把val放进去. 然后我们要单独把head和last创建出来.

好了,我们正式来介绍重写方法

2.1 遍历打印元素display()

我们需要遍历整个链表,并且打印每一个结点的值,我们先定义一个cur让它指向head,然后我们开始遍历,因为我们需要把每一个结点遍历到,因此我们循环条件是cur != null;循环内部,我们每一次循环就需要打印val并且把cur重置一下.让他指向它的下一个.

2.2 判断是否包含某个元素contains(int key)

我们判断某个元素是否在链表里面,我们就应该先遍历这个链表,每次遍历就判断cur.val是否和key值一样.如果不一样就把cur继续更新为下一个结点.

2.3 头插法addFirst(int data)

双向链表进行头插法,如图,我们只需要让node指向head,修改head.prev,和修改node.next即可.不过我们在进行头插法之前,先要对head进行判断.看它是不是空的,是我们就直接把head和last指向node即可.

2.4 尾插法addLast(int data)

此刻双向链表,我们不需要像单链表一样先找到尾巴结点,因为,我们本身就由一个last指向尾巴结点,我们直接修改即可.同时我们也要考虑head是否为null的情况,如果为null,我们直接让head和last指向node即可

2.5 插入到任意位置addIndex(int index,int data)

我们要在提供的index位置来插入元素,因为提供了下标,我们需要对下标进行合法性判断,首先判断它是否越界,然后判断是不是在第一个结点插,是的话就进行头插法,判断是不是在最后一个结点插,是的话就进行尾插法.不然的话就都是中间结点的插入,我们先找到index位置的结点,我们创建一个私有方法findIndex(int index)找到我们的index位置上的结点.

我们找到结点之后,先让node结点和前后俩个结点进行相联,node.next = cur;node.prev = cur.prev,然后我们再修改上一个节点的next和当前节点的prev,cur.prev.next = node;cur.prev = node;

2.6 删除给定值节点remove(int key)

我们删除给定值节点,必然是要遍历这个链表的,再在这个基础上进行删除,然后我们要分三种情况来进行讨论,因为如果我们不考虑头和尾的情况,假设我们删除的是最后一个节点cur.next就是空指针异常了.如果是头节点,我们cur.prev.next就会空指针异常.此时我们先讨论尾巴和中间的情况,如果是尾巴的话,我们直接让last = last.prev;并且把last.next设置为null.如果是中间,我们就通过cur作为桥梁进行删除,cur指向的就是我们当前要删除的节点,我们只需要让cur的前一个指向cur的后一个节点即可,也就是cur.prev.next = cur.next;cur.next.prev = cur.prev;

然后我们讨论头节点的情况,我们头节点,这个情况就是又要分为只有头节点一个和除了头节点还有其他节点的情况,我们先来讨论除了头节点还有其他节点的情况,我们直接让head = head.next ,并且把head.prev = null;即可,而如果只有头节点一个,我们再进行head.prev操作的时候会空指针异常,因为我们的head此时为null,不能再操作它了.因此我们直接head = head.next 即可

2.7 删除所有的给定值节点removeAll(int key)

删除所有的key,我们只需要在刚刚的基础上改一下删除尾巴节点的写法即可,我们让cur来进行操作,如果删除的是尾巴节点cur.prev.next = cur.next(此时cur.next为null),last = last.next;删除的是中间节点,cur.prev.next = cur.next;cur.next.prev=cur.prev;此时可以合并一下,如图,最后我们在每次判断完之后就让cur = cur.next ,遍历完整个链表,删除全部的key为止.

2.8 清空整个链表clear()

我们清空整个链表,需要把val值(如果是引用类型)置为空,然后我们要把每一个节点的prev,next都置为null,把head和last也置为null.我们先创建cur让它指向head,然后对链表进行遍历,我们把val设置为null(若为引用类型),我们创建temp让他指向cur的下一个节点,然后我们操作cur,让cur把它的prev和next置为空,然后我们把cur更新为tmp,最后我们要手动置空head和last.

整体代码:

package LinkedList和链表;import java.util.List;public class MyLinkedList implements Ilist{static class ListNode {public int val;public ListNode next;public ListNode prev;public ListNode(int val) {this.val = val;}}//last指向尾巴,head指向头public ListNode head;public ListNode last;
//头插法@Overridepublic 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;}}@Overridepublic void addLast(int data) {ListNode node = new ListNode(data);if(head == null) {last = node;head = node;}else {last.next = node;node.prev = last;last = node;}}@Overridepublic void addIndex(int index, int data) throws IndexIlleage{ListNode node = new ListNode(data);//检擦Index是否合法int len = size();if(index < 0 || index > len) {throw new IndexIlleage("下标越界! " + index);}if(index == 0) {//头插addFirst(data);return;}if(index == len) {//尾插addLast(data);return;}//找到cur,cur走index步ListNode cur = findIndex(index);//先修改next再修改prevnode.next = cur;node.prev = cur.prev;cur.prev.next = node;cur.prev = node;}private ListNode findIndex(int index) {ListNode cur = head;while (index != 0) {cur = cur.next;index--;}return cur;}@Overridepublic boolean contains(int key) {ListNode cur = head;while (cur != null) {if(cur.val == key) {return true;}cur = cur.next;}return false;}//TODO 删除@Overridepublic void remove(int key) {ListNode cur = head;//先找到那个和Key相等的结点while (cur != null) {//删除的是头if (head.val == key) {head = head.next;//如果只有一个结点的话,继续操作head会空指针异常if (head != null) {head.prev = null;return;}last = null;//如果只有一个结点的话head和last都得置为空return;}//删除的是尾巴if (last.val == key) {last = last.prev;last.next = null;return;}if (cur.val == key) {cur.prev.next = cur.next;cur.next.prev = cur.prev;} else {cur = cur.next;}}}//TODO 删除所有的key值@Overridepublic void removeAllKey(int key) {ListNode cur = head;//先找到那个和Key相等的结点while (cur != null) {if (cur.val == key) {if (cur == head) {//删除的是头head = head.next;if (head == null) {last = null;//删除链表只有一个结点} else {head.prev = null;//删除的链表不止一个结点}} else {cur.prev.next = cur.next;if (cur.next == null) {//删除的是尾巴last = last.prev;last.next = null;} else {cur.next.prev = cur.prev;//删除的是中间结点}}}cur = cur.next;}}@Overridepublic int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}
//TODO 清空@Overridepublic void clear() {
//    head = null;
//    last = null;//比较暴力,也能回收ListNode cur = head;while (cur != null) {
//            cur.val = null;引用数据类型ListNode tmp = cur.next;cur.prev = null;cur.next = null;cur = tmp;}//我们把 head 和 last 手动置为空head = null;last = null;}@Overridepublic void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}
}

3. Java底层的LinkedList 的使用

3.1 构造方法

方法	解释
LinkedList()	无参构造
public LinkedList(Collection<?extendsE>c)	使用其他集合容器中元素构造List

我们主要来看看第二个构造方法:Collection<? extends E > c

1. 该集合类必须实现Collection接口

2. 在第一个<>设置的类型必须是第二个<>的子类或者它自己

这样就能实现直接把另一个实例的内容作为我新的实例的内容.

我们直接看下面的例子即可.

3.2 LinkedList其他方法的介绍和使用

方法	解释
boolean add(E e)	尾插e
void add(int index,E element)	把e插入e位置
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

我们来使用一下:

package LinkedList和链表;import org.omg.PortableInterceptor.INACTIVE;import java.util.LinkedList;
import java.util.List;public class t1 {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());}
}

结果:

3.3 遍历

我们LinkedList有很多种遍历方式.

1.直接打印链表名字(因为实现了toString方法)

2.使用for-each

3.使用for循环

4.使用迭代器(也可以逆着打)

我们直接看代码

public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);System.out.println(list);System.out.println("=======");for(Integer x:list){System.out.print(x+" ");}System.out.println();System.out.println("=========");for (int i = 0;i < list.size();i++){System.out.print(list.get(i)+" ");}System.out.println();System.out.println("==============");//迭代器Iterator<Integer>  it = list.iterator();while (it.hasNext()) {System.out.print(it.next()+" ");}System.out.println();ListIterator<Integer> it1 =  list.listIterator();while (it.hasNext()) {System.out.println(it1.next());}//TODO 使用迭代器反向打印System.out.println("反向");ListIterator<Integer> it2 = list.listIterator(list.size());while (it2.hasPrevious()) {System.out.print(it2.previous()+" ");}System.out.println();

运行结果:

4. ArrayList和LinkedList的区别

这个是个面试题,我们可以有以下三种问法:

1. ArrayList和LinkedList区别是什么?

2. 顺序表和链表(分双向和单向)的区别?

3. 数组和连边的区别是什么?

如果时经常根据下标进行查找使用顺序表ArrayList,如果经常进行插入和删除操作的可以使用链表LinkedList.下面是更详细的回答

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续,物理上不一定连续
随机访问	O(1)	O(n)
头插	需要搬运元素,O(n)	只需要改变引用指向,O(1)
插入	空间不顾时需要扩容	没有容量概念
应用场景	元素高效存储+频繁访问	任意位置频繁插入和删除