java的LinkedList

发布于：2024-10-15 ⋅ 阅读:(38) ⋅ 点赞:(0)
微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

java的LinkedList

什么是LinkedList

LinkedList的官方文档
LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的结点中，然后通过引用将结点连接起来了，因此在任意位置插入或删除元素时，不需要搬移元素，效率比较高。
在这里插入图片描述
说明：

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

LinkedList的模拟实现

在这里插入图片描述

public interface IList {
    //头插法
    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();
}

public class MyLinkedList implements IList{
        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;
    
    @Override
    public void addFirst(int data) {
        
    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

    @Override
    public void display() {

    }
    
}

我们先来实现打印链表和得到链表长度

@Override
public int size() {
    ListNode cur = this.head;
    int count = 0;
    while(cur != null){
        cur = cur.next;
        count++;
    }
    return count;
}
@Override
public void display() {
    ListNode cur = this.head;
    while(cur != null){
        System.out.print(cur.val + " ");
        cur = cur.next;
    }
    System.out.println();
}

接下来实现头插法

在这里插入图片描述

@Override
public void addFirst(int data) {
    ListNode newNode = new ListNode(data);
    if(this.head == null){
        head = last = newNode;
        return;
    }
    head.prev = newNode;
    newNode.next = head;
    head = newNode;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addFirst(56);
        list.addFirst(45);
        list.addFirst(34);
        list.addFirst(23);
        list.addFirst(12);
        list.display();
        list.addFirst(33);
        list.display();
        System.out.println(list.size());
    }
    //结果为：
    //12 23 34 45 56 
    //33 12 23 34 45 56 
    //6
}

实现尾插法
在这里插入图片描述

@Override
public void addLast(int data) {
    ListNode newNode = new ListNode(data);
    if(head == null){
        head = last = newNode;
        return;
    }
    last.next = newNode;
    newNode.prev = last;;
    last = newNode;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.display();
    }
    //结果为：
    //12 23 34 45 56
}

实现任意位置插入,第一个数据节点为0号下标
在这里插入图片描述

private ListNode findIndex(int index){
    ListNode cur = this.head;
    while(index != 0){
        cur = cur.next;
        index--;
    }
    return cur;
}
@Override
public void addIndex(int index, int data) {
    int len = size();
    if(index < 0 || index > len - 1){
        return;
    }
    if(index == 0){
        addFirst(data);
        return;
    }
    if(index == len - 1){
        addLast(data);
        return;
    }
    ListNode cur = findIndex(index);
    ListNode newNode = new ListNode(data);
    newNode.next = cur;
    cur.prev.next = newNode;
    newNode.prev = cur.prev;
    cur.prev = newNode;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.display();
        list.addIndex(2,33);
        list.display();
        list.addIndex(0,33);
        list.display();
        list.addIndex(6,33);
        list.display();
        list.addIndex(8,33);
        list.display();
    }
    //结果为：
    //12 23 34 45 56
    //12 23 33 34 45 56
    //33 12 23 33 34 45 56
    //33 12 23 33 34 45 56 33
    //33 12 23 33 34 45 56 33
}

实现删除第一次出现关键字为key的节点
在这里插入图片描述

@Override
public void remove(int key) {
    ListNode cur = this.head;
    while(cur != null){
        if(cur.val == key){
            if(cur == this.head){
                head = head.next;
                if(head != null){
                    head.prev = 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 class Test {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.display();
        list.remove(12);
        list.display();
        list.remove(56);
        list.display();
        list.remove(34);
        list.display();
    }
    //结果为：
    //12 23 34 45 56
    //23 34 45 56
    //23 34 45
    //23 45
}

删除所有值为key的节点，我们只需要在删除第一次出现关键字为key的节点的代码上将return删除掉，让其循环到链表结尾

@Override
public void removeAllKey(int key) {
    ListNode cur = this.head;
    while(cur != null){
        if(cur.val == key){
            if(cur == this.head){
                head = head.next;
                if(head != null){
                    head.prev = null;
                }
            }else{
                cur.prev.next = cur.next;
                if(cur.next == null){
                    last = last.prev;
                }else{
                    cur.next.prev = cur.prev;
                }
            }
        }
        cur = cur.next;
    }
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(23);
        list.addLast(33);
        list.addLast(34);
        list.addLast(23);
        list.addLast(23);
        list.display();
        list.removeAllKey(23);
        list.display();
    }
    //结果为：
    //23 33 34 23 23
    //33 34
}

实现查找是否包含关键字key是否在双向链表当中，我们只需要遍历链表，找到返回true，没找到返回false

@Override
public boolean contains(int key) {
    ListNode cur = this.head;
    while(cur != null){
        if(cur.val == key){
            return true;
        }
        cur = cur.next;
    }
    return false;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.display();
        System.out.println(list.contains(34));
        System.out.println(list.contains(100));
    }
    //结果为：
    //12 23 34 45 56
    //true
    //false
}

接下来实现clear，我们可以直接暴力的将head和last置为null
但是最后是将每个结点的prev和last都置为null，我们需要一个curN保留下一个结点，最后还需要将head和last置为null

@Override
public void clear() {
    ListNode cur = this.head;
    while(cur != null){
        ListNode curN = cur.next;
        cur.prev = null;
        cur.next = null;
        cur = curN;
    }
    this.head = this.last = null;
}

public class Test {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(12);
        list.addLast(23);
        list.addLast(34);
        list.addLast(45);
        list.addLast(56);
        list.display();
        list.clear();
        list.display();
    }
    //结果为：
    //12 23 34 45 56
    //
}

LinkedList的使用

  1. LinkedList的构造
方法 解释
LinkedList () 无参构造
LinkedList (Collection<? extends E> c) 利用其他集合容器中元素构造List 
import java.util.ArrayList;
import java.util.LinkedList;
public class Test {
    public static void main(String[] args) {
        //构造一个空的LinkedList
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        System.out.println(list1);

        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(11);
        list2.add(22);
        list2.add(33);
        list2.add(44);
        list2.add(55);
        //使用ArrayList构造LinkedList
        LinkedList<Integer> list3 = new LinkedList<>(list2);
        System.out.println(list3);

    }
    //结果为：
    //[1, 2, 3, 4, 5]
    //[11, 22, 33, 44, 55]
}
  1. 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 
import java.util.LinkedList;
import java.util.List;
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list1 = new LinkedList<>();
        list1.add(1);   //add(elem)表示尾插
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        System.out.println(list1.size());   //5
        System.out.println(list1);      //[1, 2, 3, 4, 5]

        //在起始位置插入0
        list1.add(0,0);    //add(index,elem);在index位置插入元素elem
        System.out.println(list1);      //[0, 1, 2, 3, 4, 5]

        list1.remove();     //remove();删除第一个元素，内部调用的是removeFirst()
        System.out.println(list1);  //[1, 2, 3, 4, 5]
        list1.removeFirst();    //removeFirst();删除第一个元素
        System.out.println(list1);  //[2, 3, 4, 5]
        list1.removeLast();     //removeLast();删除最后一个元素
        System.out.println(list1);  //[2, 3, 4]
        list1.remove(1);    //remove(index);删除index位置的元素
        System.out.println(list1);  //[2, 4]

        //contains(elem):检测elem元素是否存在，如果存在返回true，否则返回false
        if(!list1.contains(1)){
            list1.add(0,1);
        }
        System.out.println(list1);  //[1, 2, 4]
        list1.addLast(1);
        System.out.println(list1);  //[1, 2, 4, 1]
        System.out.println(list1.indexOf(1));   //indexOf(elem);从前往后找第一个elem的位置 0
        System.out.println(list1.lastIndexOf(1));   //lastIndexOf(elem);从后往前找第一个elem的位置 3
        int elem = list1.get(0);    //get(index);获取指定位置元素
        System.out.println(elem);   // 1
        list1.set(0,100);   //set(index,elem);将index位置的元素设置为elem
        System.out.println(list1);  //[100, 2, 4, 1]

        //subList(from,to):用list1中[from,to)之间的元素构造一个新的LinkedList返回
        List<Integer> copy = list1.subList(0,3);
        System.out.println(list1);  //[100, 2, 4, 1]
        System.out.println(copy);   //[100, 2, 4]
        list1.clear();  //将list1中元素清空
        System.out.println(list1.size());   //0
    }
}
  1. LinkedList的遍历
public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println(list);

        System.out.println("======for=====");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();

        System.out.println("======for each=====");
        for(int x : list){
            System.out.print(x + " ");
        }
        System.out.println();

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

        System.out.println("======ListIterator=====");
        ListIterator<Integer> lit = list.listIterator();
        while(lit.hasNext()){
            System.out.print(lit.next() + " ");
        }
        System.out.println();

        System.out.println("======ListIterator拓展=====");
        ListIterator<Integer> lit2 = list.listIterator(list.size());
        while(lit.hasPrevious()){
            System.out.print(lit.previous() + " ");
        }
    }
    //结果为：
    //[1, 2, 3, 4, 5]
    //======for=====
    //1 2 3 4 5
    //======for each=====
    //1 2 3 4 5
    //======Iterator=====
    //1 2 3 4 5 
    //======ListIterator=====
    //1 2 3 4 5
    //======ListIterator拓展=====
    //5 4 3 2 1
}

ArrayList和LinkedList的区别

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

本篇文章到此，谢谢阅读，希望对您有帮助。

网站公告

今日签到

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

热门文章

最新发布