Java中LinkedList的模拟实现

目录
  • 关于LinkedList
  • 模拟实现LinkedList
    • 准备工作
    • 头插
    • 尾插
    • 在任意位置插入
    • 删除remove
    • 删除removeAll
    • 找元素下标indexOf
    • 找元素下标lastIndexOf
    • 判断链表是否包含某个元素
    • 获得链表长度
    • 链表判空
    • 清空链表

关于LinkedList

LinkedList的底层是用一个双向链表实现的,即一个结点中除了有一个引用指向下一个结点的地址,还有一个引用指向前一个结点的地址

LinkedList还有三个成员变量:

  • size,表示该链表中结点的个数
  • first,指向链表首结点
  • last,指向链表尾结点

模拟实现LinkedList

准备工作

创建静态内部类ListNode,后续创建结点都需要ListNode来创建新的结点

    private static class ListNode<E> {
        ListNode<E> pre;  //指向前一个结点
        ListNode<E> next; //指向下一个结点
        E val;  //结点的值

        public ListNode(E val){
            this.val = val;
        }
    }

创建成员变量:first,last,size

    private ListNode<E> first;  //指向链表首结点
    private ListNode<E> last;  //指向链表尾结点
    private int size;  //链表结点的个数

重写toString()方法,在进行测试方法的时候需要将链表打印出来

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        if(first == null){
            sb.append("]");
        }else {
            ListNode<E> cur = first;
            while(cur.next != null){
                sb.append(cur.val);
                sb.append(",");
                cur = cur.next;
            }
            sb.append(cur.val);
            sb.append("]");
        }
        return sb.toString();
    }

头插

在链表的头部插入结点,这里分两种情况:链表为空,链表不为空

链表为空:直接将first,last指向该结点,因为这个结点既是第一个结点,也是最后一个结点
链表不为空:将first的pre执行该结点,再将该结点的next指向first,更新first位置

在结点头插完后,更新size的长度,进行size++

    public void addFirst(E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(first == null){
            first = newNode;
            last = newNode;
        }else {
            first.pre = newNode;
            newNode.next = first;
            first = newNode;
        }
        size++;
    }

进行测试:依次头插入1,2,3,4,打印list

        MyLinkedList<Integer> list = new MyLinkedList<>();
        list.addFirst(1);
        list.addFirst(2);
        list.addFirst(3);
        list.addFirst(4);
        System.out.println(list);

打印结果:因为是头插,所以打印4,3,2,1

尾插

  • 在链表的尾部插入结点,分两种情况:链表为空,链表不为空
  • 链表为空:直接将first,last指向该结点,该结点既是链表的首结点,又是最后一个结点
  • 链表不为空last的next执行该节点,该节点的pre指向last,更新last位置
  • 在结点尾插完后,更新size的长度,进行size++
    public void addLast(E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(first == null){
            first = newNode;
            last = newNode;
        }else {
            last.next = newNode;
            newNode.pre = last;
            last = newNode;
        }
        size++;
    }

进行测试:依次尾插入1,2,3,4,打印list

        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        System.out.println(list);

打印结果:因为是尾插,所以打印1,2,3,4

在任意位置插入

这里分三种情况讨论:在第一个位置插入,在最后一个位置插入,在其他位置插入

在第一个位置插入:相当于头插,调用addFirst()方法
在最后一个位置插入:相当于尾插,调用addLast()方法

在其他位置插入看下图解析

    public boolean addIndex(int index,E e){
        ListNode<E> newNode = new ListNode<>(e);
        if(index < 0 && index > size){
            throw new IndexOutOfBoundsException("addIndex:下标越界");
        }
        if(index == size){
            addLast(e);
        }else if(index == 0){
            addFirst(e);
        }else {
            ListNode<E> cur = first;
            for(int i = 0;i < index;i++){
                cur = cur.next;
            }
            newNode.pre = cur.pre;
            newNode.next = cur;
            newNode.pre.next = newNode;
            cur.pre = newNode;
            size++;
        }
        return true;
    }

进行测试:原来链表为1,2,3,4,在位置0插入1,在位置5插入5,在位置3插入3

        list.addIndex(0,1);
        list.addIndex(4,5);
        list.addIndex(3,3);
        System.out.println(list);

打印结果:打印为1,1,2,3,3,4,5

删除remove

这里分为三种情况:删除的是第一个元素,删除的是最后一个元素,删除其他元素

  • 删除一个元素:将first指向first的next,再将first的pre指向null
  • 删除最后一个元素:将last更新为last的pre位置,再将last的next指向null

删除其他位置元素:参照下图解析

删除完后,进行size--操作

    public void remove(E e){
        ListNode<E> cur = first;
        while(cur != null){
            if(e.equals(cur.val)){
                break;
            }
            cur = cur.next;
        }
        if(cur == first){
            first = first.next;
            first.pre = null;
        }else if(cur == last){
            last = last.pre;
            last.next = null;
        }else {
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        size--;
    }

进行测试:原链表为1,2,3,4,5,删除1,删除5,删除3

        list.remove(1);
        list.remove(5);
        list.remove(3);
        System.out.println(list);

打印结果:打印2,4

删除removeAll

这个与删除一次出现元素e的做法差不多,只是在找到第一次出现元素e时,将它删掉,继续遍历链表

    public void removeAll(E e){
        ListNode<E> cur = first;
        while(cur != null){
            if(cur.val.equals(e)){
                if(cur == first){
                    first = first.next;
                    first.pre = null;
                }else if(cur == last){
                    last = last.pre;
                    last.next = null;
                }else {
                    cur.pre.next = cur.next;
                    cur.next.pre = cur.pre;
                }
                size--;
            }
            cur = cur.next;
        }
    }

进行测试:链表为1,2,1,3,1,将所有的1全部删掉

        list.removeAll(1);
        System.out.println(list);

打印结果:链表中的元素只剩下2,3

找元素下标indexOf

创建一个下标index,从0开始增加,每遍历一个元素进行index++,如果遍历的元素是要找的元素则返回index,当遍历完链表没有要找的元素时,返回-1

    public int indexOf(E e){
        ListNode<E> cur = first;
        int index = 0;
        while(cur != null){
            if(e.equals(cur.val)){
                return index;
            }else {
                index++;
                cur = cur.next;
            }
        }
        return -1;
    }

进行测试:链表为1,2,3,4,5,找3的位置和6的位置

        System.out.println(list.indexOf(3));
        System.out.println(list.indexOf(6));

打印结果:3在下标为2的位置,6不在该链表中,故返回-1

找元素下标lastIndexOf

这个从链表尾部往前遍历,创建index值为size-1,当元素不为我们要找的元素时,index--,找到返回index,当遍历完整个链表都没有找到时,返回-1

    public int lastIndexOf(E e){
        ListNode<E> cur = last;
        int index = size-1;
        while(cur != null){
            if(e.equals(cur.val)){
                return index;
            }else {
                cur = cur.pre;
                index--;
            }
        }
        return -1;
    }

进行测试:链表为1,2,3,3,4,5,找3的位置和6的位置

        System.out.println(list.lastIndexOf(3));
        System.out.println(list.lastIndexOf(6));

 打印结果:最后一个3的下标为3,6不在该链表中

判断链表是否包含某个元素

这里可以调用indexOf方法,看返回的是不是-1,如果不是-1则说明链表包含该元素,如果返回的是-1,说明链表不包含该元素

    public boolean contains(E e){
        return -1 != indexOf(e);
    }

进行测试:链表为1,2,3,4,5,判断该链表是否包含2和6

        boolean ret = list.contains(2);
        boolean ret1 = list.contains(6);
        System.out.println(ret);
        System.out.println(ret1);

输出结果:2在链表中,6不在链表中

获得链表长度

直接返回size即可

    public int size(){
        return size;
    }

进行测试:返回空链表的size,和有元素的size

        list.clear();
        System.out.println(list.size());
        list.addFirst(1);
        System.out.println(list.size());

 打印结果:

链表判空

判断链表为空有两种方式:判断size是否为0或者判断first是否指向null

    public boolean isEmpty(){
        //return size==0;
        return first==null;
    }

进行测试:看有元素的链表是否为空,和空链表是否为空

        list.clear();
        list.addFirst(1);
        boolean ret1 = list.isEmpty();
        System.out.println(ret1);
        list.clear();
        boolean ret2 = list.isEmpty();
        System.out.println(ret2);

打印结果:

清空链表

清空操作就是将first指向null,将last指向null,将size置0

    public void clear(){
        first = null;
        last = null;
        size = 0;
    }

进行测试:执行清空操作,打印list

        list.clear();
        System.out.println(list);

打印结果:链表中没有元素

到此这篇关于Java中LinkedList的模拟实现的文章就介绍到这了,更多相关Java中 LinkedList的模拟内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 解析Java中的队列和用LinkedList集合模拟队列的方法

    API中对队列的说明: public interface Queue<E> extends Collection<E> 在处理元素前用于保存元素的 collection.除了基本的 Collection 操作外,队列还提供其他的插入.提取和检查操作.每个方法都存在两种形式:一种抛出异常(操作失败时),另一种返回一个特殊值(null 或 false,具体取决于操作).插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的:在大多数实现中,插入操作不会失败. 队列通常(但

  • Java中LinkedList的模拟实现

    目录 关于LinkedList 模拟实现LinkedList 准备工作 头插 尾插 在任意位置插入 删除remove 删除removeAll 找元素下标indexOf 找元素下标lastIndexOf 判断链表是否包含某个元素 获得链表长度 链表判空 清空链表 关于LinkedList LinkedList的底层是用一个双向链表实现的,即一个结点中除了有一个引用指向下一个结点的地址,还有一个引用指向前一个结点的地址 LinkedList还有三个成员变量: size,表示该链表中结点的个数 fir

  • Java中LinkedList详解和使用示例_动力节点Java学院整理

    第1部分 LinkedList介绍 LinkedList简介 LinkedList 是一个继承于AbstractSequentialList的双向链表.它也可以被当作堆栈.队列或双端队列进行操作. LinkedList 实现 List 接口,能对它进行队列操作. LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用. LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆. LinkedList 实现java.io.Serial

  • Java中LinkedList原理代码解析

    本文研究的主要是Java中LinkedList原理的相关内容,具体介绍如下. 一句话概括,Java中的LinkedList其实就是使用双向链表,LinkedList的基本操作就是对双向链表的操作. 上面可以清晰的看出,链表中每个元素对应一个节点,节点里面包含三部分,一个是前一个节点的引用,一个是元素内容,一个是后一个节点的引用. 向链表中添加元素的过程就是在链表尾部追加一个节点 void linkLast(E e) { final Node<E> l = last; final Node<

  • Java中LinkedList真的是查找慢增删快

    测试结果 废话不多说,先上测试结果.作者分别在ArrayList和LinkedList的头部.尾部和中间三个位置插入与查找100000个元素所消耗的时间来进行对比测试,下面是测试结果 (感谢@Hosalo的指正,在这里说明一下测试的环境,尾部插入是在空表的基础上测试的,头部和中间位置插入是在已存在100000个元素的表上进行测试的) 插入 查找 ArrayList尾部 26ms 4ms ArrayList头部 2887ms 3ms ArrayList中间 1936ms 4ms LinkedLis

  • java中LinkedList使用迭代器优化移除批量元素原理

    本文主要介绍了java中LinkedList使用迭代器优化移除批量元素原理,分享给大家,具体如下: public interface Iterator<E> { /** *是否还有下一个元素 */ boolean hasNext(); /** *下一个元素 */ E next(); /** * 从集合中删除最后一个返回的元素 */ default void remove() { throw new UnsupportedOperationException("remove"

  • 如何实现Java中一个简单的LinkedList

    LinkedList与ArrayList都是List接口的具体实现类.LinkedList与ArrayList在功能上也是大体一致,但是因为两者具体的实现方式不一致,所以在进行一些相同操作的时候,其效率也是有差别的. 对于抽象的数据结构--线性表而言,线性表分为两种,一种是顺序存储结构的顺序表,另一种是通过指针来描述其逻辑位置的链表. 针对于具体的Java实现: 顺序存储的顺序表是用数组来实现的,以数组为基础进行封装各种操作而形成的List为ArrayList 链表是用指针来描述其逻辑位置,在J

  • java 中模拟UDP传输的发送端和接收端实例详解

    java 中模拟UDP传输的发送端和接收端实例详解 一.创建UDP传输的发送端 1.建立UDP的Socket服务: 2.将要发送的数据封装到数据包中: 3.通过UDP的Socket服务将数据包发送出去: 4.关闭Socket服务. import java.io.IOException; import java.net.DatagramPacket; import java.net.DatagramSocket; import java.net.InetAddress; public class

  • java 中ArrayList与LinkedList性能比较

    java 中ArrayList与LinkedList性能比较 今天看一框架的代码,看到有些 可以使用ArrayList的地方 使用的是 LinkedList,用到的情景是在一个循环里面进行顺序的插入操作. 众所周知java里面List接口有两个实现ArrayList 和 LinkedList,他们的实现原理分别是c语言中介绍的数组和链表. 正如学习数据结构时的认识,对于插入操作,链表的结构更高效,原因是可以通过修改节点的指针 就可以完成插入操作, 而不像数组, 需要把插入位置之后的数组元素依次后

  • Java中ArrayList和LinkedList的遍历与性能分析

    前言 通过本文你可以了解List的五种遍历方式及各自性能和foreach及Iterator的实现,加深对ArrayList和LinkedList实现的了解.下面来一起看看吧. 一.List的五种遍历方式 1.for each循环 List<Integer> list = new ArrayList<Integer>(); for (Integer j : list) { // use j } 2.显示调用集合迭代器 List<Integer> list = new Ar

随机推荐