LinkedList底层结构
LinkedList底层实现了双向链表和双向队列特点 可以添加任意元素,包括null,元素可以重复 线程不安全,没有实现同步
LinkedList底层操作机制
LinkedList底层维护了一个双向链表 LinkedList中维护了两个属性first和last分别指向首结点和尾结点 每个结点(Node 对象),里面又维护了prev、next、item三个属性,其中通过prev指向前一个,通过next指向后一个结点,最终实现双向链表 所以LinkedList的元素的增加和删除,不是通过数组完成的,相对来说效率较高 模拟一个简单的双向链表
@SuppressWarnings ( { "all" } )
public class Journey {
public static void main ( String [ ] args) {
Node life = new Node ( "life" ) ;
Node is = new Node ( "is" ) ;
Node journey = new Node ( "a journey" ) ;
life. next = is;
is. next = journey;
journey. pre = is;
is. pre = life;
Node first = life;
Node last = journey;
while ( true ) {
if ( first== null ) {
break ;
}
System . out. println ( first) ;
first = first. next;
}
System . out. println ( "==========演示链表添加数据==========" ) ;
Node definitely = new Node ( "definitely" ) ;
definitely. next = is;
definitely. pre = life;
life. next = definitely;
is. pre = definitely;
first = life;
while ( true ) {
if ( first== null ) {
break ;
}
System . out. println ( first) ;
first = first. next;
}
}
}
class Node {
public Object item;
public Node next;
public Node pre;
public Node ( Object name) {
this . item = name;
}
public String toString ( ) {
return "Node name=" + item;
}
}
LinkedList的增删改查
@SuppressWarnings ( { "all" } )
public class Journey {
public static void main ( String [ ] args) {
LinkedList list = new LinkedList ( ) ;
for ( int i = 0 ; i <= 2 ; i++ ) {
list. add ( i) ;
}
System . out. println ( list) ;
list. remove ( ) ;
System . out. println ( list) ;
list. add ( "kerwin" ) ;
System . out. println ( list) ;
list. remove ( 1 ) ;
System . out. println ( list) ;
list. set ( 1 , "fun" ) ;
System . out. println ( list) ;
list. add ( "Dopamine" ) ;
System . out. println ( list. get ( 2 ) ) ;
System . out. println ( list. getFirst ( ) ) ;
System . out. println ( list. getLast ( ) ) ;
System . out. println ( "==================================================" ) ;
Iterator iterator = list. iterator ( ) ;
while ( iterator. hasNext ( ) ) {
Object obj = iterator. next ( ) ;
System . out. println ( obj) ;
}
for ( Object o: list) {
System . out. println ( "els->" + o) ;
}
for ( int i = 0 ; i < list. size ( ) ; i++ ) {
System . out. println ( "normal-For->" + list. get ( i) ) ;
}
}
}
对应的各个方法的源码剖析
public boolean add ( E e) {
linkLast ( e) ;
return true ;
}
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;
}
}
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++ ;
}
这时候,你会发现,加了两个元素之后,first指向第一个结点,而last指向第二个结点,这不正合心意??
public E remove ( ) {
return removeFirst ( ) ;
}
public E removeFirst ( ) {
final Node < E > f = first;
if ( f == null )
throw new NoSuchElementException ( ) ;
return unlinkFirst ( f) ;
}
private E unlinkFirst ( Node < E > f) {
final E element = f. item;
final Node < E > next = f. next;
f. item = null ;
f. next = null ;
first = next;
if ( next == null )
last = null ;
else
next. prev = null ;
size-- ;
modCount++ ;
return element;
}
ArrayList和LinkedList比较
如何选择ArrayList和LinkedList?
如果我们改查的操作多,选择ArrayList 如果我们增删的操作多,选择LinkedList 一般来说,程序中,大部分是查询,因此大多数情况下,会选择ArrayList 在一个项目中,根据业务灵活选择,也可能这样,有可能一个模块用的是ArrayList,另一个模块使用的是LinkedList