深入入IAEA底层LinkedList

发布于：2024-05-10 ⋅ 阅读:(25) ⋅ 点赞:(0)

✅作者简介：大家好，我是再无B～U～G，一个想要与大家共同进步的男人😉😉

🍎个人主页：再无B～U～G-CSDN博客

目标：

1.掌握LinkedList

2.简单模拟实现LinkedList

1.LinkedList的使用

1.1 什么是LinkedList

LinkedList 的官方文档

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

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

【说明】 

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

4. LinkedList 的任意位置插入和删除元素时效率比较高，不用移动（时间复杂度为 O(1)）
5. LinkedList比较适合任意位置插入的场景

 2 LinkedList的使用

2.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.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 
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);
    // 在起始位置插入0
    list.add(0, 0); // add(index, elem): 在index位置插入元素elem
    System.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，否则返回false
    if(!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位置的元素设置为elem
    System.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());
}

2.3. 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);
  
    System.out.println(list.size());

    //正常遍历
    for (int i = 0; i < size; i++) {
            System.out.print(list.get(i)+" ");
            //list.remove(i);
    }

    // foreach遍历
    for (int e:list) {
        System.out.print(e + " ");
    }

    System.out.println("====Iterator===");
    Iterator<Integer> it = list.iterator();
    while (it.hasNext()) {
        System.out.print(it.next() +" ");
    }
    System.out.println();

    // 使用迭代器遍历---正向遍历
    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();
}

3. ArrayList和LinkedList的区别

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

4.LinkedList的模拟实现

总体结构

4.1双向链表代码节点结构

4.2得到双向链表的长度

遍历打印

4.3查找是否包含关键字key是否在单链表当中

4.4头插法

4.5尾插法

4.6任意位置前面插入

附带两个私有函数

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

4.8删除所有值为key的节点

4.9释放链表

 

在IDEA中，LinkedList的底层逻辑是双向链表，可以当做栈和堆使用。

5.代码

MyLinkedList类
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 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;
        }
        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 void addFirst(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            //是不是第一次插入节点
            head = 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 = last = node;
        }else {
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }
    //任意位置前面插入
    public 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;
    }
    //找到双向链表key节点
    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的节点
    public 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 {
                        //head == null 证明只有1个节点
                        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的节点
    public 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;
                    }
                }
                //return;//删完一个就走
            }
            cur = cur.next;
        }
    }
    //释放链表
    public 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;
    }
    
}

IndexNotLegalException类
public class IndexNotLegalException extends RuntimeException{
    public IndexNotLegalException() {
    }

    public IndexNotLegalException(String message) {
        super(message);
    }
}

Test类

import java.util.LinkedList;
import java.util.List;
//双向链表
public class Test {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        myLinkedList.addLast(4);
        myLinkedList.addLast(5);

        myLinkedList.addIndex(3,99);

        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.addLast(1);
        myLinkedList.removeAllKey(1);
        myLinkedList.display();
    }
}

好了今天就到这里了，感谢观看。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布