首页 > 其他分享 >8-LinkedList

8-LinkedList

时间:2024-08-22 18:16:22浏览次数:10  
标签:Node LinkedList 元素 list println public

LinkedList实现类

常用方法及使用

        /*
        LinkedList常用方法
        增加: addFirst(E e)  addLast(E e)
             offer(E e)  offerFirst(E e)  offerLast(E e)
        删除: poll()
             pollFirst() pollLast()
             removeFirst() removeLast()
        修改:
        查看: element()
             getFirst()  getLast()
             indexOf(Object o)  lastIndexOf(Object o)
             peek()
             peekFirst()  peekLast()
        判断:
         */

        //创建一个LinkedList集合对象
        LinkedList<String> list = new LinkedList<>();//LinkedList是一个泛型类,在创建实例时推荐把泛型加上
        list.add("aaaaa");//填数据
        list.add("bbbbb");
        list.add("ccccc");
        list.add("ddddd");
        list.add("eeeee");
        list.add("bbbbb");
        list.add("fffff");
        //LinkedList可以添加重复数据

        //向头添加一个元素addFirst
        list.addFirst("jj");
        //向尾添加一个元素addLast
        list.addLast("hh");

        //offer也是添加元素
        list.offer("kk");//添加元素在尾端
        list.offerFirst("pp");//头部
        list.offerLast("rr");//尾
        System.out.println(list);

        //删除
        System.out.println(list.poll());//删除头上元素并且将删除的元素输出
        System.out.println(list.pollFirst());//同上
        System.out.println(list.removeFirst());//同上
        System.out.println(list.pollLast());//删除尾元素并将删除的元素输出
        System.out.println(list.removeLast());//同上
        System.out.println(list);
        /*
        疑问:功能都一样,为啥有两个?
        做以下操作
        list.clear();//清空集合
        System.out.println(list);
        System.out.println(list.pollFirst());//输出null--->JDK1.6开始,新版本的,提高的代码的健壮性
        list.removeFirst();//报错--->抛出异常,早期的方法
         */

        //集合的遍历
        System.out.println("----------------");
        //1.普通for
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        System.out.println("----------------");
        //2.增强for
        for (String s :
                list) {
            System.out.println(s);
        }
        System.out.println("----------------");
        //3.迭代器
        /*  Iterator<String> it = list.iterator();//自动加的泛型String,因为泛型确定
        while (it.hasNext()){
            System.out.println(it.next());
        }*/  //下面的方式更好,节省了内存,it作用完就释放
        for (Iterator<String> it = list.iterator(); it.hasNext();){
            System.out.println(it.next());//it.next()方法直接进行下一步迭代,故上面for循环不写迭代语句
        }

底层

对比

ArrayList

ArrayList:数据结构

  • 物理结构:紧密结构(在内存里紧挨着一个一个的)
  • 逻辑结构:线性表(数组)

LinkedList

LinkedList:数据结构

  • 物理结构:跳转结构
  • 逻辑结构:线性表(链表)
    • LinkedList的链表是双向的

LinkedList底层链表

  • 链表:双向链表

例:放入三个元素:“aa”,“bb”,“cc”

  1. 将放入的元素“aa”封装成对象
    • 前一个元素地址null |当前存入元素 "aa" |后一个元素地址null
    • 以上整个这个对象才是链表中的一个节点
  2. 后面元素依次放

模拟LinkedList链表

  • 节点类Node
public class Node {//节点类
    //三个属性:
    //上一个元素的地址:
    private Node pre;//上一个元素实际是一个节点
    //当前存入的元素:
    private Object obj;//可能是各式各样的类型,故是Object类型
    //下一个元素地址
    private Node next;

    //属性私有化--->提供set、get方法
    public Node getPre() {
        return pre;
    }

    public void setPre(Node pre) {
        this.pre = pre;
    }

    public Object getObj() {
        return obj;
    }

    public void setObj(Object obj) {
        this.obj = obj;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    //提供一个toString,展示元素到底有什么数据
    @Override
    public String toString() {
        return "Node{" +
                "pre=" + pre +
                ", obj=" + obj +
                ", next=" + next +
                '}';
    }
}
  • 实现LinkedList集合
public class MyLinkedList {//创建自己的LinkedList集合,不跟系统的名一样
    //链中一定有一个首节点
    Node first;
    //链中一定有一个尾节点
    Node last;
    //计数器
    int count = 0;
    //提供一个构造器
    public MyLinkedList() {
    }
    //添加元素的方法:
    public void add(Object o){
        if(first == null){//证明你添加的元素是第一个节点
            //将添加的元素封装为一个Node对象:
            Node n = new Node();
            n.setPre(null);
            n.setObj(o);
            n.setNext(null);
            //当前链中第一个节点变为n
            first = n;
            //当前链中最后一个节点变为n
            last = n;
        }else {//证明已经不是链中第一个节点了
            //将添加的元素封装为一个Node对象:
            Node n = new Node();
            n.setPre(last);//n的上一个节点一定是当前链中的最后一个节点last
            n.setObj(o);
            n.setNext(null);
            //当前链中的最后一个节点的下一个元素要指向n
            last.setNext(n);
            //将最后一个节点变成n
            last = n;
        }
        //链中元素数量加1
        count++;
    }

    //得到集合中元素的数量
    public int getSize(){
        return count;
    }

    //通过下标得到元素;
    public Object get(int index){
        /*
        链表没有直接的下标--->
        通过从头元素计数开始往下数--->
        得到对应位置元素
         */
        //获取链表的头元素
        Node n = first;
        //循环到对应元素跳出
        for (int i = 0; i < index; i++) {
            n = n.getNext();
        }
        return n.getObj();
    }
}

class Test{
    public static void main(String[] args) {
        //创建一个MyLinkedList集合对象
        MyLinkedList m1 = new MyLinkedList();
        m1.add("aa");
        m1.add("bb");
        m1.add("cc");
        System.out.println(m1.getSize());
        System.out.println(m1.get(2));
    }
}

LinkedList的API

public class LinkedList<E>{//E是一个泛型,具体的类型要在实例化的时候才会最终确定
    transient int size = 0;//集合中元素数量
    //Node的内部类
    private static class Node<E> {
        E item;//当前元素
        Node<E> next;//下一个元素地址
        Node<E> prev;//上一个元素地址

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    transient Node<E> first;//首节点
    transient Node<E> last;//尾节点
    //空构造器
    public LinkedList() {
    }
    //添加元素操作
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    void linkLast(E e) {//添加的元素e
        final Node<E> l = last;//将链表中的last节点给l 如果是第一个元素的化 l为null
        //将元素封装为一个Node具体的对象
        final Node<E> newNode = new Node<>(l, e, null);
        //将链表的last节点指向新的创建的对象:
        last = newNode;
        if (l == null)//如果添加的是第一个节点
            first = newNode;//将链表的first节点指向为新节点
        else//如果不是第一个节点
            l.next = newNode;//将l的下一个指向为新的节点
        size++;//集合中元素数量加1操作
        modCount++;
    }
    ///获取集合中元素数量
    public int size() {
        return size;
    }
    //通过索引得到元素
    public E get(int index) {
        checkElementIndex(index);//健壮性考虑
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // size>>1 位运算-->提高效率,二分--->提高效率
        //如果index在链表的前半段,那么从前往后找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {//如果index在链表的后半段,那么从后往前找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
}

标签:Node,LinkedList,元素,list,println,public
From: https://www.cnblogs.com/Mc9r4dy/p/18374474

相关文章

  • 集合及数据结构第七节————LinkedList的模拟实现与使用
    系列文章目录集合及数据结构第七节————LinkedList的模拟实现与使用LinkedList的模拟实现与使用无头双向链表实现什么是LinkedListLinkedList的使用LinkedList的遍历ArrayList和LinkedList的区别文章目录系列文章目录集合及数据结构第七节————LinkedList的模......
  • ArrayList 和 LinkedList 的区别是什么
    数据结构实现:ArrayList是动态数组的数据结构实现,而LinkedList是双向链表的数据结构实现。随机访问效率:ArrayList比LinkedList在随机访问的时候效率要高,因为LinkedList是线性的数据存储方式,所以需要移动指针从前往后依次查找。增加和删除效率:在非首尾的增加和删除操......
  • LinkedList模拟栈数据结构的集合,并测试
    packagecom.shujia.day13;importjava.util.LinkedList;/*LinkedList请用LinkedList模拟栈数据结构的集合,并测试栈:先进后出题目的要求是:自己创建一个类,将LinkedList作为成员变量,将来创建自己的类对象,使用自己的方法,但是底层用的是LinkedList中的方法......
  • LinkedList
    packagecom.shujia.day13;importjava.util.Iterator;importjava.util.LinkedList;/*Collection:-List(有序【指的是存储和取出的顺序是一致的】且可以发生重复,且有索引的概念)-ArrayList:底层数据结构是数组,查询快,增删慢,线程不安全的,效率高......
  • 【数据结构】LinkedList与链表
    目录链表1、链表的概念及结构 2、LinkedList的使用2、1什么是LinkedList2、2LinkedList的使用3、LinkedList的遍历4、LinkedList的模拟实现 5、ArrayList和LinkedList的区别上篇已经熟悉了ArrayList的使用,ArrayList底层使用数组来存储元素。由于其底层是一段连续......
  • 面试考点分析( ArrayList和LinkedList对比)
    1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。2.两者都是线程不安全,都实现了Collection接口。3.数据结构:ArrayList是基于动态数组的数据结构,LinkedList是基于双向链表的数据结构。性能:ArrayList支持随机访问,查询快,增删慢,查询的时间复杂度为O(1),插......
  • LeetCode | 160 Intersection of two linkedlists
    https://github.com/dolphinmind/datastructure/tree/datastructure-linkedlist分析判断两个链表是否相交,转换成了双指针相遇的问题。还是那句话,双指针的本质是遍历,走的路其实一样/***解决两个链接不相交而陷入无限循环的情况*初......
  • 使用LinkedList实现队列和栈
    LinkedList底层是由双向链表实现的,因此可以支持Queue和Stack。本文讨论的实现基于JDK8源码。实现QueueLinkedList本身实现了Queue接口。入队方法签名接口说明(JDK手册)代码实现概括(JDK8)boolean add(Ee)将指定的元素插入此队列(如果立即可行且不会违反容量限制),在......
  • Android开发 - List类中LinkedList实现类解析
    什么是LinkedListLinkedList是List接口的一个具体实现类,它基于双向链表数据结构来实现元素的存储和操作主要特点双向链表:LinkedList使用双向链表作为底层数据结构,每个节点(Node)包含对前一个和后一个节点的引用。这使得在LinkedList中插入和删除元素的效率很高,因为只......
  • 《Java初阶数据结构》----3.<线性表---LinkedList与链表>
    目录前言一、链表的简介1.1链表的概念1.2链表的八种结构 重点掌握两种1.3单链表的常见方法三、单链表的模拟实现四、LinkedList的模拟实现(双链表)4.1 什么是LinkedList4.2LinkedList的使用五、ArrayList和LinkedList的区别 前言   大家好,我目前在学习......