你的位置:首页 > Java教程

[Java教程]LinkedList深入学习


  • 实现方法


首先LinkedList继承了AbstractSequentialList实现了List<E>, Deque<E>, Cloneable, java.io.Serializable接口

LinkedList是一种常用的list实现,他是基于双向链表(双向链表:集合中的每一个元素都知道其前一个元素和后一个元素的位置)来实现的,在LinkedList中,用一个内部的Entity类来代表集合中的元素,元素的值赋给element属性,Entity中的next属性指向元素的后一个元素,Entity中的previous属性指向元素的前一个元素,基于这样的机制能够实现快速的移动集合中的元素。

  • 构造方法


在创建LinkedList对象时候,首先创建一个element为null,next为null,previous为null的entity对象,并赋值给全局的header属性

在执行构造器的时候,LinkedList将head的next及previous都指向header,以形成双向链表所需要的闭环    

 

 

  • 插入对象:add(E)


每次通过add方法增加元素的时候,要做的就是创建一个Entity对象,并将这个Entity的next指向header,previous指向head.previous,在完成自己的next、previuos的设置后,同时将位于当前元素的后一元素的previous指向自己,并将位于当前元素的前一元素的next指向自己,这样就保持了双向链表的闭环。

LinkedList的add方法不像ArrayList那样,要考虑扩容以及复制数组的问题,但是每增加一个元素,都会创建一个新的Entity对象,并修改相邻的两个元素的属性

 

  • 删除对象:remove(E)


要删除LinkedList中的一个元素,首先同样遍历整个集合中的元素,遍历和寻找元素的方法和ArrayList基本相同,寻找到之后删除就比ArrayList简单多了。

删除的时候,值需要直接删除链表上的当前元素,并将当前元素中的element、previous、next设置为空,并不需要移动元素的位置

  • 获取单个对象:get(index)


LinkedList的元素不是存储在数组中的,所以他的get操作过程比ArrayList复杂,在执行get操作时,首先判断传入的index值是否小于0或大于等于当前LinkedList的size值,,不符合则抛出越界异常;如符合条件,判断当前获取的位置是否小于LinkedList值的一般,如果小于,则从头一直找到index位置对应的元素,大于则从尾部往前查找

  • 遍历对象:iterator()


Iterator方法由父类的AbsttractList实现,当调用此方法的时候,每次都会创建一个ListItr对象,创建时候该对象符合保存cursor位置

  • 判断对象是否存在:contains(E)


为了判断元素是否存在与集合中,采用的方法是遍历所有元素,如果传入的值为null,则找到为null的元素,传入值为非null,则使用equals进行判断,找到则返回true

  • 注意要点


    • LinkedList是基于双向链表的机制实现的
    • LinkedList是非线程安全的
    • LinkedList执行插入元素的时候,会创建一个Entity对象,并切换相应元素的前后元素的引用,在查找元素的时候,进行遍历链表,删除元素的时候,遍历链表找到删除的元素