`
yuyiming1986
  • 浏览: 63306 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

LinkedList源码分析

阅读更多

 

LinkedList源码分析

 

 

LinkedList是动态数组的另一种实现,底层以双向循环链表为实现基础,它的优势在于可以快速的删除和添加元素,不需要像ArrayList那样移动大量的元素,但对于查找元素需要逐个遍历链表中的元素,进行匹配。所以LinkedList适用于频繁删除和添加元素,较少查找元素的应用场景。

 

 

LinkedList内部使用Entry<E>来封装双向循环链表结点.LinkedList头结点的定义:

        private transient Entry<E> header = new Entry<E>(null, null, null);

 

Entry是一个静态内部类,用于描述双向链表的结点

//有三个域:element对象引用或者基本类型的值,也就是结点的data域
//         next域指向节点的后继
//         previous指向结点的前驱
private static class Entry<E> {
    
	E element;
	Entry<E> next;
	Entry<E> previous;

	Entry(E element, Entry<E> next, Entry<E> previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
 }
 

1.LinkedList构造函数

 

    //LinkedList采用的内部数据结构是双向循环链表,结点使用Entry描述.

 //初始化时,将结点的前驱和后续都指向自己(header).形成了循环。
 public LinkedList() {
       header.next = header.previous = header;
 }

 

2.访问方法-getFirst(),GetLast(),get(int index)

 

   getFirst()方法

 

 

 //取得双向链表中的第一个元素,也就是header的后继域next域指向的元素
 public E getFirst() {
      
	if (size==0)
	    throw new NoSuchElementException();

	return header.next.element;
 }
 

  getLast()方法

   //取得双向链表的最后一个元素,也就是header前驱动域previous指向的元素.

  public E getLast()  {
	if (size==0)
	    throw new NoSuchElementException();

	return header.previous.element;
  }
 
 

   get(index)方法

//通过下标来查找元素

    public E get(int index) {
        return entry(index).element;
    }

      private Entry<E> entry(int index) {

        //对于参数index的合法性进行校验
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Entry<E> e = header;
        //查找指定位置的双向链表中的节点,从header->next开始算作是0
        //如果查找的位置比size/2小,则顺着找,只需要比对一半的元素
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
            
        //如果指定位置比size/2大,则逆着找,从header->previous开始向前查找
        //最多,也只需要比对一半的元素。
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }

 

   3.remove方法

 

  remove(Entry<E> e)方法,在双向循环链表中删除指定结点e

 

  private E remove(Entry<E> e) {

        //如果指定删除的节点,是头结点,则抛出异常,头节点是不可能被删除的.
	if (e == header)
	    throw new NoSuchElementException();

        /*********************************
	 *  |--next---->| ----next--->|
	 * [P]         [e]           [N]
	 *  |<---pre----|<----pre-----|   
	**********************************/
	
	//将在e前驱和后继之间,剔出对e的关联
        E result = e.element;
	e.previous.next = e.next;
	e.next.previous = e.previous;
	
	//小心的释放当前被删除节点持有的关于其它节点的引用
        e.next = e.previous = null;
        e.element = null;
	size--;
	modCount++;

        return result;
    }
 

  由remove(Entry<E> e)方法衍生出removeFirst(Entry<E> e)和removeLast(Entry<E> e)

 

  removeFirst()方法+removeLast()方法

 

   //删除链表第一个元素,也就是header的后继

  public E removeFirst() {
	return remove(header.next);
  }

  //删除链表的最后一个元素,也就是header的前驱
  public E removeLast() {
	return remove(header.previous);
  }

 

 

    remove(Object o)首先是查找到指定的对象所在的节点,然后调用remove(Entry)

     public boolean remove(Object o) {

        //对于目标元素是null分开处理
        if (o==null) {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
      
        //如果没有找到目标元素,则返回false
        return false;
    }

 

 

   

4.add方法

 

    addBefore(E o, Entry<E> e)方法,在e结点和e.previous之间添加添加元素o.

 

    private Entry<E> addBefore(E o, Entry<E> e) {

    
        //在newEntry的构造函数中已经将next,previous指向正确的位置
        //Entry(E element, Entry<E> next, Entry<E> previous) {
	//    this.element = element;
	//    this.next = next;
	//    this.previous = previous;
	//}
       
        Entry<E> newEntry = new Entry<E>(o, e, e.previous);
	
	//这里还需要更新newEntry前驱节点的next域
	//和newEntry后继节点的previous域
	newEntry.previous.next = newEntry;
	newEntry.next.previous = newEntry;
	size++;
	modCount++;
	return newEntry;
    }
 

    由addBefore(E o, Entry<E> e)衍生出addLast(), addFrist()方法

 

    //在双向循环链表头添加元素,也就是header.next和heder之间

    public void addFirst(E o) {
	addBefore(o, header.next);
    }


   //在双向循环链表尾添加元素,也就是header和header.previous之间
     public void addLast(E o) {
	addBefore(o, header);
    }
 

   通常的add(E)方法

 

    //直接就将元素存放在header.previous与header之间

   public boolean add(E o) {

	addBefore(o, header);
        return true;
    }
 

 

  5. 查找目标元素位置

        //查找指定的元素在链表中的位置,只能是遍历双向循环链表的每个节点,并将节点data取出来比对

    //查找元素,如果是查找null,采用==;如果是查找其它对象则使用equals()
    public int indexOf(Object o) {
        int index = 0;
        if (o==null) {
            for (Entry e = header.next; e != header; e = e.next) {
                if (e.element==null)
                    return index;
                index++;
            }
        } else {
            for (Entry e = header.next; e != header; e = e.next) {
                if (o.equals(e.element))
                    return index;
                index++;
            }
        }
        return -1;
    }

 

 

 

 

 

 

 

 

 

 

分享到:
评论

相关推荐

    LinkedList源码分析_016.pdf

    《LinkedList源码解析》 LinkedList是Java集合框架中的一员,它是AbstractSequentialList的子类,同时也实现了List、Deque和Cloneable、Serializable接口。LinkedList作为双向链表,支持快速的添加、删除元素,尤其...

    Java集合系列之LinkedList源码分析

    Java集合系列之LinkedList源码分析 概述: 本文详细介绍了Java集合系列之LinkedList的源码分析,主要介绍了LinkedList的底层实现、成员变量、构造器、增删改查方法等。LinkedList是一种基于双向链表的数据结构,...

    Java LinkedList源码分析

    简介  LinkedList 是一个常用的集合类,用于顺序存储元素。 LinkedList 经常和 ArrayList 一起被提及。...本文分析 LinkedList 的具体实现。  继承关系  public class LinkedList  extends AbstractS

    LinkedList源码学习分析

    《LinkedList源码学习分析》 LinkedList作为Java集合框架中的一员,是基于链表数据结构实现的线程不安全容器。本文将深入探讨LinkedList的实现原理、核心方法的代码实现,并对比ArrayList,理解其特性和使用场景。 ...

    Java 集合之LinkedList源码分析

    LinkedList是通过节点的连接实现链表的数据结构,向linkedList中插入或删除元素的速度是特别快,而随机访问的速度相对较慢,这个是由于链表本身的性质造成的,在链表中,每个节点都包含了前一个节点的引用,后一个...

    【死磕Java集合】-集合源码分析.pdf

    一、LinkedList源码分析 LinkedList是一种以双向链表实现的List,它除了作为List使用,还可以作为队列或者栈来使用。它实现了List、Queue和Deque接口,使其具有多种使用场景。 LinkedList的继承体系中,它继承了...

    LinkedList 部分源码

    ### LinkedList部分源码解析 #### 一、简介 `LinkedList`是Java集合框架的一个重要组成部分,它基于双向链表实现,既支持`List`接口也实现了`Deque`接口,因此可以作为列表、栈或者队列使用。双向链表的每个节点...

    JDK1.6中Arraylist,Vector,LinkedList源码

    源码分析时,可以关注以下几个关键点: 1. 容量管理:观察ArrayList和Vector如何进行扩容,了解它们扩容的策略和成本。 2. 插入和删除:比较ArrayList、Vector和LinkedList在插入和删除元素时的代码实现,分析时间...

    计算机后端-Java-Java核心基础-第24章 集合01 15. LinkedList的源码分析.avi

    计算机后端-Java-Java核心基础-第24章 集合01 15. LinkedList的源码分析.avi

    Java基于JDK 1.8的LinkedList源码详析

    "Java基于JDK 1.8的LinkedList源码详析" LinkedList是Java中一个非常重要的数据结构,基于双向链表实现,适用于...通过对LinkedList源码的分析,我们可以更好地了解其内部实现机制和特点,并更好地应用于实际开发中。

    ArrayList-LinkedList-源码.rar

    《ArrayList与LinkedList源码解析》 在Java编程中,ArrayList和LinkedList是两种常见的动态数组,它们都是Java集合框架的一部分,提供了对元素存储和操作的功能。本篇将深入探讨ArrayList和LinkedList的内部实现...

    Map+List+ArrayList+LinkedList Java源码

    **源码分析** 深入研究这些类的源码,可以帮助我们理解它们是如何在内存中组织数据以及如何执行各种操作的。例如,`HashMap`的哈希函数如何计算元素的桶位置,`ArrayList`如何调整其容量,以及`LinkedList`如何通过...

    Android+上百实例源码分析以及开源分析+集合打包3

    在Android开发领域,深入理解和应用源码分析以及开源库的运用是提升技能的关键步骤。"Android+上百实例源码分析以及开源分析+集合打包3"这个资源提供了丰富的学习材料,涵盖了多个方面,旨在帮助开发者更好地理解和...

    java LinkedList源码详解及实例

    3. **源码分析**: - `getFirst()`和`getLast()`通过直接访问`first`和`last`属性来获取元素,这两个属性分别保存链表的第一个和最后一个节点。 - `removeFirst()`和`removeLast()`通过`unlinkFirst(Node&lt;E&gt; f)`和...

    Android_上百实例源码分析以及开源分析_集合打包4

    在Android开发领域,源码分析和开源项目的理解是提升技能的关键步骤。"Android_上百实例源码分析以及开源分析_集合打包4"这个资源显然旨在帮助开发者深入掌握Android应用程序的内部工作原理,以及如何利用开源库优化...

    分析Java中ArrayList与LinkedList列表结构的

    **LinkedList源码分析** LinkedList是基于双向链表实现的,每个元素都是一个Node对象,包含前一个节点、后一个节点和存储的值。相比于ArrayList,LinkedList在插入和删除操作上更高效,因为不需要移动大量元素,但...

    JUC并发编程与源码分析视频课.zip

    《JUC并发编程与源码分析视频课》是一门深入探讨Java并发编程的课程,主要聚焦于Java Util Concurrency(JUC)库的使用和源码解析。JUC是Java平台提供的一组高级并发工具包,它极大地简化了多线程编程,并提供了更...

    Java中的ArrayList的底层源码解读、LinkedList、Vector的区别介绍

    能学到什么:ArrayList的源码分析,自动扩容和自动缩容的源码分析,相关参数的深度解析,从是什么,为什么,怎么做三个角度进行讲解,用通俗易懂的白话进行介绍,LinkedList和Vector以及ArrayList的区别以及使用场景...

    源码解析jdk7.0集合:LinkedList的底层实现原理.pdf

    在具体源码分析中,Node节点内部类的实现是LinkedList的基础。Node内部类的定义方式是: ```java private static class Node&lt;E&gt; { E item; Node&lt;E&gt; next; Node&lt;E&gt; prev; Node(Node&lt;E&gt; prev, E element, Node...

Global site tag (gtag.js) - Google Analytics