集合及数据结构第七节————LinkedList的模拟实现与使用

系列文章目录

集合及数据结构第七节————LinkedList的模拟实现与使用

LinkedList的模拟实现与使用

1. 无头双向链表实现
2. 什么是LinkedList
3. LinkedList的使用
4. LinkedList的遍历
5. ArrayList和LinkedList的区别

---

---

一、LinkedList的模拟实现

1.无头双向链表实现

定义接口

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

定义双向链表的内部类

    static class ListNode {//将节点定义成内部类public int val;//数据域public ListNode next;//后驱节点（引用类型）public  ListNode prev;//前驱节点public ListNode(int val) {this.val = val;//没有初始化next默认为null（因为next是引用数据类型）}}public ListNode head;//头节点public ListNode last;//尾节点

接口的实现

头插法的时间复杂度为O（1）

头插法

思路：

第一次插入时head和last都指向这个节点

代码实现：

    public void addFirst(int data) {;//头插法ListNode node = new ListNode(data);//创建一个node节点用来存放插入的数据if(head == null){//插入第一个数据this.head = node;this.last = node;}else {//有其他节点，进行头插node.next = this.head;//先绑定后面更安全this.head.prev = node;this.head = node;}}

尾插法

尾插法的时间复杂度为O（1）

思路：

第一次插入时head和last都指向这个节点

代码实现：

    public void addLast(int data) {//尾插法ListNode node = new ListNode(data);//创建一个node节点用来存放插入的数据if(head == null){//插入第一个数据this.head = node;this.last = node;}else {//有其他节点，进行尾插last.next = node;//先绑定后面更安全node.prev = this.last;this.last = node;}}

任意位置插入,第一个数据节点为0号下标

思路：

1. 检查index是否合法
2. 找到cur节点（cur走index步 ）（新增一个private修饰的searchIndex方法来找到index位置节点）
3. 插入node节点

public class AddIndexLocationWrong extends  RuntimeException{// 检查index是否合法（输入下标不合法）public AddIndexLocationWrong(String message){super(message);}
}

    private ListNode searchIndex(int index){//找到index位置节点ListNode cur = this.head;//创建一个临时节点来替head节点完成工作//从而避免head = null的情况出现while (index != 0){cur = cur.next;//让cur指向下一个节点index--;}return cur;}

    public void addIndex(int index, int data) {;//任意位置插入,第一个数据节点为0号下标int len = size();if(index < 0 || index > len){//如果输入的index对应节点没有数据，抛出异常throw  new AddIndexLocationWrong("输入的index位置不合法" + index);}if (index == 0) {//在开头插入直接调用头插法addFirst(data);return;}if (index == len){//在结尾插入，直接调用尾插法addLast(data);return;}ListNode cur = searchIndex(index);//新建一个cur节点存放找到的index位置的节点ListNode node = new ListNode(data);//创建一个node节点用来存放插入的数据//插入数据（先修改next就一定不会出错）node.next = cur;//让node的next后驱指向curcur.prev.next  = node;//让插入前cur的前一个节点的next后驱指向nodenode.prev = cur.prev;//让node的next前驱指向插入前cur的前一个节点cur.prev = node;//让cur的next前驱指向node}

查找是否包含关键字key是否在双向链表当中

   public boolean contains(int key) {//查找是否包含关键字key是否在单链表当中ListNode cur = this.head;//创建一个临时节点来替head节点完成工作//从而避免head = null的情况出现while (cur != null){if (cur.value == key){return true;}cur = cur.next;}return false;}

删除第一次出现关键字为key的节点

思路：
一般情况下

删除的是第一个节点

删除最后一个节点

代码实现：

    public void remove(int key) {//删除第一次出现关键字为key的节点ListNode cur = this.head;while (cur != null){if(cur.val ==key) {//cur的val与key相等时if(cur == head){//删除的是第一个节点head = head.next;//头节点向后移动（当链表中只有一个节点时，相当于把head置空让第一个节点不再被head引用）if (head == null){//当链表中只有一个节点时// （不加这个判断条件会导致else中的语句在只有一个节点时,空指针异常）last = null;//当链表中只有一个节点时,last置空让第一个节点不再被last引用}else {head.prev = null;//移动后的头节点的前驱置空（第一个节点不在被引用，会被自动化回收）}}else {//删除的不是第一个节点cur.prev.next = cur.next;//让cur的前一个节点的next后驱指向cur的后一个节点if(cur.next == null){//删除的是最后一个节点,把last置空让第一个节点不再被last引用last = last.prev;}else {//删除的是中间节点cur.next.prev = cur.prev;//让cur的后一个节点的前驱指向cur的前一个节点}}return;//删除结束后退出}else {cur = cur.next;}}}

删除所有值为key的节点

    public void removeAllKey(int key) { //删除所有值为key的节点ListNode cur = this.head;while (cur != null){if(cur.val ==key) {//cur的val与key相等时（删完一个后不退出，直到遍历完整个链表）if(cur == head){//删除的是第一个节点head = head.next;//头节点向后移动（当链表中只有一个节点时，相当于把head置空让第一个节点不再被head引用）if (head == null){//当链表中只有一个节点时// （不加这个判断条件会导致else中的语句在只有一个节点时,空指针异常）last = null;//当链表中只有一个节点时,last置空让第一个节点不再被last引用}else {head.prev = null;//移动后的头节点的前驱置空（第一个节点不在被引用，会被自动化回收）}}else {//删除的不是第一个节点cur.prev.next = cur.next;//让cur的前一个节点的next后驱指向cur的后一个节点if(cur.next == null){//删除的是最后一个节点,把last置空让第一个节点不再被last引用last = last.prev;}else {//删除的是中间节点cur.next.prev = cur.prev;//让cur的后一个节点的前驱指向cur的前一个节点}}}cur = cur.next;}}

得到双向链表的长度

        ListNode cur = this.head;//创建一个临时节点来替head节点完成工作//从而避免head = null的情况出现int count = 0;//用来计数while (cur != null){count++;cur = cur.next;}return count ;

清空

1. 直接把头节点和尾节点置空（不推荐）
2. 把每个节点的每个域都置空

    public void clear() {//清空链表ListNode cur = head;while (cur != null){ListNode temp = cur.next;//让temp指向cur的后驱指向的节点，让清空操纵正常进行//cur.val = null;//cur.prev = null;cur.next = null;cur = temp;}head = null;last = null;}

打印链表的数据

要创建一个临时节点来替head节点完成工作，从而避免head = null的情况出现

public void display() {//打印链表的数据ListNode cur = this.head;//创建一个临时节点来替head节点完成工作//从而避免head = null的情况出现while (cur != null){//打印的停止条件System.out.print(cur.value + " ");cur = cur.next;//让head指向下一个节点}System.out.println();
}

二、.LinkedList的使用

1.什么是LinkedList

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

在集合框架中，LinkedList也实现了List接口，具体如下：

【说明】

1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场

2.LinkedList的使用（ * * ）

1. LinkedList的构造

public static void main(String[] args) {// 构造一个空的LinkedListList<Integer> list1 = new LinkedList<>();List<String> list2 = new java.util.ArrayList<>();list2.add("JavaSE");list2.add("JavaWeb");list2.add("JavaEE");// 使用ArrayList构造LinkedListList<String> list3 = new LinkedList<>(list2);
}

2. LinkedList的其他常用方法介绍

方法	解释
void addLast(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

（? extends E）是指 ：？是不是E本身或者E的子类

首先创建一个Integer类型的链表表并存入一些数字，并打印一下链表的大小和链表

inkedList<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);

---

---

在起始位置插入0

            list.add(0, 0); // add(index, elem): 在index位置插入元素elemSystem.out.println(list);

---

---

remove(): 删除第一个元素，内部调用的是removeFirst()

			list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()System.out.println(list);

---

---

removeFirst(): 删除第一个元素

			list.removeFirst(); // removeFirst(): 删除第一个元素System.out.println(list);

---

---

removeLast(): 删除最后元素

            list.removeLast(); // removeLast(): 删除最后元素System.out.println(list);

---

---

remove(index): 删除index位置的元素

            list.remove(1); // remove(index): 删除index位置的元素System.out.println(list);

---

---

contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false

            if(!list.contains(1)){//1如果不存在就进入iflist.add(0, 1);}list.add(1);//内部调用的是linkLast(e);System.out.println(list);

---

---

indexOf(elem): 从前往后找到第一个elem的位置

            System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置

---

---

lastIndexOf(elem): 从后往前找第一个1的位置

System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置

---

---

get(index): 获取指定位置元素

            int elem = list.get(0); // get(index): 获取指定位置元素System.out.println(elem);

---

---

set(index, elem): 将index位置的元素设置为elem

            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);copy.add( 0,5656);System.out.println(list);System.out.println(copy);

---

---

将list中元素清空

            list.clear(); // 将list中元素清空System.out.println(list.size());

---

完整代码：

      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.LinkedList的遍历

ArrayList 可以使用三方方式遍历：for循环+下标、foreach、使用迭代器

    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());//for循环+下标遍历for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();
// foreach遍历for (int e:list) {System.out.print(e + " ");}System.out.println();
// 使用迭代器遍历---正向遍历 要导包--》import java.util.ListIterator;ListIterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next()+ " ");}System.out.println();
// 使用反向迭代器---反向遍历   要导包--》import java.util.ListIterator;ListIterator<Integer> rit = list.listIterator(list.size());while (rit.hasPrevious()){System.out.print(rit.previous() +" ");}System.out.println();}

三、ArrayList和LinkedList的区别

如果经常根据下标进行查找的，可以使用顺序表Array list。
如果经常进行插入和删除的，可以使用链表Linked list。