文档章节

LinkedList的了解

laohng1995
 laohng1995
发布于 2017/07/25 09:17
字数 725
阅读 13
收藏 0

 LinkedList<E>  继承AbstractSequentialList<E> 实现 List<E>, Deque<E>, Cloneable, java.io.Serializable

属性:

    transient int size = 0;                                    //尺寸
    
关于结点
     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 LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

方法
  
   public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);                  //初始化的时候index=0

        Object[] a = c.toArray();                    //类型转化
        int numNew = a.length;                       //传入的数组的长度
        if (numNew == 0)
            return false;
 
        Node<E> pred, succ;                          //succ指向当前需要插入节点的位置,pred指向其前一个节点
        if (index == size) {
            succ = null;
            pred = last;                             //如果该链表没有内容尾指针指向头
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);                    //创建一个Node
            if (pred == null)
                first = newNode;                                            //将创建的结点给予头指针
            else
                pred.next = newNode;                                        //前一个结点的下一个结点newNode
            pred = newNode;                                                 //指针指向下一个结点                                          
        }

        if (succ == null) {
            last = pred;                                                    //last指针指向最后一个元素
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
=====================================================

     public void clear() {
        for (Node<E> x = first; x != null; ) {                               
            Node<E> next = x.next;                                        //获取下一个值
            x.item = null;                                                //全部值都设为空
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

   public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

   Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)                               //遍历到指定位置
                x = x.next;
            return x;                                                     //返回指定位置的结点
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    public int indexOf(Object o) {                                       //匹配Object o
        int index = 0;
        if (o == null) {                                                  //空的话,直接匹配空
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {               //匹配o
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;                                                        //没有找到
    }

     public E peek() {                                                    //检索出头指针指向的内容
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    public E element() {                                                  //得到头指针的内容
        return getFirst();
    }
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    public E removeFirst() {                                               //移除头指针
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;                                         //获取结点的内容
        final Node<E> next = f.next;                                      //获取该节点的尾指针
        f.item = null;                                                    //清空该节点
        f.next = null; // help GC
        first = next;                                                     //将头指针指向该节点
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    public int size() {
        return size;
    }


   =======================================
   public boolean add(E e) {
        linkLast(e);
        return true;
    }

   void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

 ==============================================
public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);                         //获取并删除头指针
    }

© 著作权归作者所有

共有 人打赏支持
laohng1995
粉丝 11
博文 34
码字总数 28594
作品 0
南岸
程序员
java学习笔记--类ArrayList和LinkedList的实现

在集合Collection下的List中有两个实现使用的很频繁,一个是ArrayList,另一个是LinkedList,在学习中肯定都会有这样的疑问:什么时候适合使用ArrayList,什么时候用LinkedList?这时,我们就需...

UseBing
2017/08/09
0
0
LinkedList工作原理

1.学习LinkedList的必要性 在ArrayList工作原理中,我们了解到ArrayList和LinkedList是List接口的两个重要实现。并且ArrayList是一个动态数组的实现。因此ArrayList在队列中插入和删除元素方...

kukudeku
2016/09/03
107
0
ArrayList、linklist、list的区别

List是一个接口,ArrayList和LinkedList是两个实现类,他们实现的方式不一样,其实LinkedList才是真正的链表(如果不清楚什么是链表,需要了解一下相关数据结构的知识,这不是一两句话能说清楚...

随智阔
2014/03/04
0
0
LinkedList为什么在头部和尾部添加或删除元素很快?ArrayList为什么有索引查询就快?

我对这两个集合的结构还是挺了解的,比如LinkedList是一个链表,每个节点存储上个节点和下个节点的位置还有业务数据。ArrayList里边维护的是一个数组。但是一到他们的特性我最感觉理解不了,...

belizer
06/21
0
0
【Java入门提高篇】Day27 Java容器类详解(九)——LinkedList详解

  这次介绍一下List接口的另一个践行者——LinkedList,这是一位集诸多技能于一身的List接口践行者,可谓十八般武艺,样样精通,栈、队列、双端队列、链表、双向链表都可以用它来模拟,话不...

弗兰克的猫
08/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

jetbrains系产品IDEA:mac上面提示快捷键设置

原因 由于Mac上面的Ctrl+空格变成输入法切换的快捷键,在使用IDEA的过程中,代码提示很不方便,需要使用option+/这种传统eclipse上面的代码提示快捷键作为主要快捷键。 怎么修改? 移除【opt...

亚林瓜子
34分钟前
0
0
Exclipse 输出结果时换行

System.out.println(f1 + "\n" + d1 + "\n" + d2);

笑丶笑
34分钟前
1
0
怎样治疗标签不能触发onblur事件

I realize this was over a year ago, but it showed up for me in Google while trying to solve this same issue. It seems Chrome does not consider some elements, like body and ancho......

Weijuer
37分钟前
0
0
vue常见库安装

移动设备上的浏览器默认会在用户点击屏幕大约延迟300毫秒后才会触发点击事件,这是为了检查用户是否在做双击。为了能够立即响应用户的点击事件,才有了FastClick。 安装fastclick npm insta...

林夏夕
39分钟前
0
0
kafka 教程(三) kafka Java API 编程

下午写

MrPei
40分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部