Java中LinkedList详解和使用示例_动力节点Java学院整理
第1部分 linkedlist介绍
linkedlist简介
linkedlist 是一个继承于abstractsequentiallist的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
linkedlist 实现 list 接口,能对它进行队列操作。
linkedlist 实现 deque 接口,即能将linkedlist当作双端队列使用。
linkedlist 实现了cloneable接口,即覆盖了函数clone(),能克隆。
linkedlist 实现java.io.serializable接口,这意味着linkedlist支持序列化,能通过序列化去传输。
linkedlist 是非同步的。
linkedlist构造函数
// 默认构造函数 linkedlist() // 创建一个linkedlist,保护collection中的全部元素。 linkedlist(collection<? extends e> collection)
linkedlist的api
linkedlist的api boolean add(e object) void add(int location, e object) boolean addall(collection<? extends e> collection) boolean addall(int location, collection<? extends e> collection) void addfirst(e object) void addlast(e object) void clear() object clone() boolean contains(object object) iterator<e> descendingiterator() e element() e get(int location) e getfirst() e getlast() int indexof(object object) int lastindexof(object object) listiterator<e> listiterator(int location) boolean offer(e o) boolean offerfirst(e e) boolean offerlast(e e) e peek() e peekfirst() e peeklast() e poll() e pollfirst() e polllast() e pop() void push(e e) e remove() e remove(int location) boolean remove(object object) e removefirst() boolean removefirstoccurrence(object o) e removelast() boolean removelastoccurrence(object o) e set(int location, e object) int size() <t> t[] toarray(t[] contents) object[] toarray()
abstractsequentiallist简介
在介绍linkedlist的源码之前,先介绍一下abstractsequentiallist。毕竟,linkedlist是abstractsequentiallist的子类。
abstractsequentiallist 实现了get(int index)、set(int index, e element)、add(int index, e element) 和 remove(int index)这些函数。这些接口都是随机访问list的,linkedlist是双向链表;既然它继承于abstractsequentiallist,就相当于已经实现了“get(int index)这些接口”。
此外,我们若需要通过abstractsequentiallist自己实现一个列表,只需要扩展此类,并提供 listiterator() 和 size() 方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的 hasnext、next、hasprevious、previous 和 index 方法即可。
第2部分 linkedlist数据结构
linkedlist的继承关系
java.lang.object java.util.abstractcollection<e> java.util.abstractlist<e> java.util.abstractsequentiallist<e> java.util.linkedlist<e> public class linkedlist<e> extends abstractsequentiallist<e> implements list<e>, deque<e>, cloneable, java.io.serializable {}
linkedlist与collection关系如下图:
linkedlist的本质是双向链表。
(01) linkedlist继承于abstractsequentiallist,并且实现了dequeue接口。
(02) linkedlist包含两个重要的成员:header 和 size。
header是双向链表的表头,它是双向链表节点所对应的类entry的实例。entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。
size是双向链表中节点的个数。
第3部分 linkedlist源码解析(基于jdk1.6.0_45)
为了更了解linkedlist的原理,下面对linkedlist源码代码作出分析。
在阅读源码之前,我们先对linkedlist的整体实现进行大致说明:
linkedlist实际上是通过双向链表去实现的。既然是双向链表,那么它的顺序访问会非常高效,而随机访问效率比较低。
既然linkedlist是通过双向链表的,但是它也实现了list接口{也就是说,它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。linkedlist是如何实现list的这些接口的,如何将“双向链表和索引值联系起来的”?
实际原理非常简单,它就是通过一个计数索引值来实现的。例如,当我们调用get(int location)时,首先会比较“location”和“双向链表长度的1/2”;若前者大,则从链表头开始往后查找,直到location位置;否则,从链表末尾开始先前查找,直到location位置。
这就是“双线链表和索引值联系起来”的方法。
好了,接下来开始阅读源码(只要理解双向链表,那么linkedlist的源码很容易理解的)。
package java.util; public class linkedlist<e> extends abstractsequentiallist<e> implements list<e>, deque<e>, cloneable, java.io.serializable { // 链表的表头,表头不包含任何数据。entry是个链表类数据结构。 private transient entry<e> header = new entry<e>(null, null, null); // linkedlist中元素个数 private transient int size = 0; // 默认构造函数:创建一个空的链表 public linkedlist() { header.next = header.previous = header; } // 包含“集合”的构造函数:创建一个包含“集合”的linkedlist public linkedlist(collection<? extends e> c) { this(); addall(c); } // 获取linkedlist的第一个元素 public e getfirst() { if (size==0) throw new nosuchelementexception(); // 链表的表头header中不包含数据。 // 这里返回header所指下一个节点所包含的数据。 return header.next.element; } // 获取linkedlist的最后一个元素 public e getlast() { if (size==0) throw new nosuchelementexception(); // 由于linkedlist是双向链表;而表头header不包含数据。 // 因而,这里返回表头header的前一个节点所包含的数据。 return header.previous.element; } // 删除linkedlist的第一个元素 public e removefirst() { return remove(header.next); } // 删除linkedlist的最后一个元素 public e removelast() { return remove(header.previous); } // 将元素添加到linkedlist的起始位置 public void addfirst(e e) { addbefore(e, header.next); } // 将元素添加到linkedlist的结束位置 public void addlast(e e) { addbefore(e, header); } // 判断linkedlist是否包含元素(o) public boolean contains(object o) { return indexof(o) != -1; } // 返回linkedlist的大小 public int size() { return size; } // 将元素(e)添加到linkedlist中 public boolean add(e e) { // 将节点(节点数据是e)添加到表头(header)之前。 // 即,将节点添加到双向链表的末端。 addbefore(e, header); return true; } // 从linkedlist中删除元素(o) // 从链表开始查找,如存在元素(o)则删除该元素并返回true; // 否则,返回false。 public boolean remove(object o) { if (o==null) { // 若o为null的删除情况 for (entry<e> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e); return true; } } } else { // 若o不为null的删除情况 for (entry<e> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } // 将“集合(c)”添加到linkedlist中。 // 实际上,是从双向链表的末尾开始,将“集合(c)”添加到双向链表中。 public boolean addall(collection<? extends e> c) { return addall(size, c); } // 从双向链表的index开始,将“集合(c)”添加到双向链表中。 public boolean addall(int index, collection<? extends e> c) { if (index < 0 || index > size) throw new indexoutofboundsexception("index: "+index+ ", size: "+size); object[] a = c.toarray(); // 获取集合的长度 int numnew = a.length; if (numnew==0) return false; modcount++; // 设置“当前要插入节点的后一个节点” entry<e> successor = (index==size ? header : entry(index)); // 设置“当前要插入节点的前一个节点” entry<e> predecessor = successor.previous; // 将集合(c)全部插入双向链表中 for (int i=; i<numnew; i++) { entry<e> e = new entry<e>((e)a[i], successor, predecessor); predecessor.next = e; predecessor = e; } successor.previous = predecessor; // 调整linkedlist的实际大小 size += numnew; return true; } // 清空双向链表 public void clear() { entry<e> e = header.next; // 从表头开始,逐个向后遍历;对遍历到的节点执行一下操作: // () 设置前一个节点为null // () 设置当前节点的内容为null // () 设置后一个节点为“新的当前节点” while (e != header) { entry<e> next = e.next; e.next = e.previous = null; e.element = null; e = next; } header.next = header.previous = header; // 设置大小为0 size = 0; modcount++; } // 返回linkedlist指定位置的元素 public e get(int index) { return entry(index).element; } // 设置index位置对应的节点的值为element public e set(int index, e element) { entry<e> e = entry(index); e oldval = e.element; e.element = element; return oldval; } // 在index前添加节点,且节点的值为element public void add(int index, e element) { addbefore(element, (index==size ? header : entry(index))); } // 删除index位置的节点 public e remove(int index) { return remove(entry(index)); } // 获取双向链表中指定位置的节点 private entry<e> entry(int index) { if (index < 0 || index >= size) throw new indexoutofboundsexception("index: "+index+ ", size: "+size); entry<e> e = header; // 获取index处的节点。 // 若index < 双向链表长度的1/2,则从前先后查找; // 否则,从后向前查找。 if (index < (size >> 1)) { for (int i = ; i <= index; i++) e = e.next; } else { for (int i = size; i > index; i--) e = e.previous; } return e; } // 从前向后查找,返回“值为对象(o)的节点对应的索引” // 不存在就返回-1 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; } // 从后向前查找,返回“值为对象(o)的节点对应的索引” // 不存在就返回-1 public int lastindexof(object o) { int index = size; if (o==null) { for (entry e = header.previous; e != header; e = e.previous) { index--; if (e.element==null) return index; } } else { for (entry e = header.previous; e != header; e = e.previous) { index--; if (o.equals(e.element)) return index; } } return -1; } // 返回第一个节点 // 若linkedlist的大小为0,则返回null public e peek() { if (size==) return null; return getfirst(); } // 返回第一个节点 // 若linkedlist的大小为0,则抛出异常 public e element() { return getfirst(); } // 删除并返回第一个节点 // 若linkedlist的大小为,则返回null public e poll() { if (size==0) return null; return removefirst(); } // 将e添加双向链表末尾 public boolean offer(e e) { return add(e); } // 将e添加双向链表开头 public boolean offerfirst(e e) { addfirst(e); return true; } // 将e添加双向链表末尾 public boolean offerlast(e e) { addlast(e); return true; } // 返回第一个节点 // 若linkedlist的大小为,则返回null public e peekfirst() { if (size==) return null; return getfirst(); } // 返回最后一个节点 // 若linkedlist的大小为,则返回null public e peeklast() { if (size==) return null; return getlast(); } // 删除并返回第一个节点 // 若linkedlist的大小为,则返回null public e pollfirst() { if (size==0) return null; return removefirst(); } // 删除并返回最后一个节点 // 若linkedlist的大小为0,则返回null public e polllast() { if (size==0) return null; return removelast(); } // 将e插入到双向链表开头 public void push(e e) { addfirst(e); } // 删除并返回第一个节点 public e pop() { return removefirst(); } // 从linkedlist开始向后查找,删除第一个值为元素(o)的节点 // 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点 public boolean removefirstoccurrence(object o) { return remove(o); } // 从linkedlist末尾向前查找,删除第一个值为元素(o)的节点 // 从链表开始查找,如存在节点的值为元素(o)的节点,则删除该节点 public boolean removelastoccurrence(object o) { if (o==null) { for (entry<e> e = header.previous; e != header; e = e.previous) { if (e.element==null) { remove(e); return true; } } } else { for (entry<e> e = header.previous; e != header; e = e.previous) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } // 返回“index到末尾的全部节点”对应的listiterator对象(list迭代器) public listiterator<e> listiterator(int index) { return new listitr(index); } // list迭代器 private class listitr implements listiterator<e> { // 上一次返回的节点 private entry<e> lastreturned = header; // 下一个节点 private entry<e> next; // 下一个节点对应的索引值 private int nextindex; // 期望的改变计数。用来实现fail-fast机制。 private int expectedmodcount = modcount; // 构造函数。 // 从index位置开始进行迭代 listitr(int index) { // index的有效性处理 if (index < 0 || index > size) throw new indexoutofboundsexception("index: "+index+ ", size: "+size); // 若 “index 小于 ‘双向链表长度的一半'”,则从第一个元素开始往后查找; // 否则,从最后一个元素往前查找。 if (index < (size >> )) { next = header.next; for (nextindex=; nextindex<index; nextindex++) next = next.next; } else { next = header; for (nextindex=size; nextindex>index; nextindex--) next = next.previous; } } // 是否存在下一个元素 public boolean hasnext() { // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。 return nextindex != size; } // 获取下一个元素 public e next() { checkforcomodification(); if (nextindex == size) throw new nosuchelementexception(); lastreturned = next; // next指向链表的下一个元素 next = next.next; nextindex++; return lastreturned.element; } // 是否存在上一个元素 public boolean hasprevious() { // 通过元素索引是否等于,来判断是否达到开头。 return nextindex != ; } // 获取上一个元素 public e previous() { if (nextindex == ) throw new nosuchelementexception(); // next指向链表的上一个元素 lastreturned = next = next.previous; nextindex--; checkforcomodification(); return lastreturned.element; } // 获取下一个元素的索引 public int nextindex() { return nextindex; } // 获取上一个元素的索引 public int previousindex() { return nextindex-; } // 删除当前元素。 // 删除双向链表中的当前节点 public void remove() { checkforcomodification(); entry<e> lastnext = lastreturned.next; try { linkedlist.this.remove(lastreturned); } catch (nosuchelementexception e) { throw new illegalstateexception(); } if (next==lastreturned) next = lastnext; else nextindex--; lastreturned = header; expectedmodcount++; } // 设置当前节点为e public void set(e e) { if (lastreturned == header) throw new illegalstateexception(); checkforcomodification(); lastreturned.element = e; } // 将e添加到当前节点的前面 public void add(e e) { checkforcomodification(); lastreturned = header; addbefore(e, next); nextindex++; expectedmodcount++; } // 判断 “modcount和expectedmodcount是否相等”,依次来实现fail-fast机制。 final void checkforcomodification() { if (modcount != expectedmodcount) throw new concurrentmodificationexception(); } } // 双向链表的节点所对应的数据结构。 // 包含部分:上一节点,下一节点,当前节点值。 private static class entry<e> { // 当前节点所包含的值 e element; // 下一个节点 entry<e> next; // 上一个节点 entry<e> previous; /** * 链表节点的构造函数。 * 参数说明: * element —— 节点所包含的数据 * next —— 下一个节点 * previous —— 上一个节点 */ entry(e element, entry<e> next, entry<e> previous) { this.element = element; this.next = next; this.previous = previous; } } // 将节点(节点数据是e)添加到entry节点之前。 private entry<e> addbefore(e e, entry<e> entry) { // 新建节点newentry,将newentry插入到节点e之前;并且设置newentry的数据是e entry<e> newentry = new entry<e>(e, entry, entry.previous); newentry.previous.next = newentry; newentry.next.previous = newentry; // 修改linkedlist大小 size++; // 修改linkedlist的修改统计数:用来实现fail-fast机制。 modcount++; return newentry; } // 将节点从链表中删除 private e remove(entry<e> e) { if (e == header) throw new nosuchelementexception(); 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; } // 反向迭代器 public iterator<e> descendingiterator() { return new descendingiterator(); } // 反向迭代器实现类。 private class descendingiterator implements iterator { final listitr itr = new listitr(size()); // 反向迭代器是否下一个元素。 // 实际上是判断双向链表的当前节点是否达到开头 public boolean hasnext() { return itr.hasprevious(); } // 反向迭代器获取下一个元素。 // 实际上是获取双向链表的前一个节点 public e next() { return itr.previous(); } // 删除当前节点 public void remove() { itr.remove(); } } // 返回linkedlist的object[]数组 public object[] toarray() { // 新建object[]数组 object[] result = new object[size]; int i = ; // 将链表中所有节点的数据都添加到object[]数组中 for (entry<e> e = header.next; e != header; e = e.next) result[i++] = e.element; return result; } // 返回linkedlist的模板数组。所谓模板数组,即可以将t设为任意的数据类型 public <t> t[] toarray(t[] a) { // 若数组a的大小 < linkedlist的元素个数(意味着数组a不能容纳linkedlist中全部元素) // 则新建一个t[]数组,t[]的大小为linkedlist大小,并将该t[]赋值给a。 if (a.length < size) a = (t[])java.lang.reflect.array.newinstance( a.getclass().getcomponenttype(), size); // 将链表中所有节点的数据都添加到数组a中 int i = ; object[] result = a; for (entry<e> e = header.next; e != header; e = e.next) result[i++] = e.element; if (a.length > size) a[size] = null; return a; } // 克隆函数。返回linkedlist的克隆对象。 public object clone() { linkedlist<e> clone = null; // 克隆一个linkedlist克隆对象 try { clone = (linkedlist<e>) super.clone(); } catch (clonenotsupportedexception e) { throw new internalerror(); } // 新建linkedlist表头节点 clone.header = new entry<e>(null, null, null); clone.header.next = clone.header.previous = clone.header; clone.size = 0; clone.modcount = 0; // 将链表中所有节点的数据都添加到克隆对象中 for (entry<e> e = header.next; e != header; e = e.next) clone.add(e.element); return clone; } // java.io.serializable的写入函数 // 将linkedlist的“容量,所有的元素值”都写入到输出流中 private void writeobject(java.io.objectoutputstream s) throws java.io.ioexception { // write out any hidden serialization magic s.defaultwriteobject(); // 写入“容量” s.writeint(size); // 将链表中所有节点的数据都写入到输出流中 for (entry e = header.next; e != header; e = e.next) s.writeobject(e.element); } // java.io.serializable的读取函数:根据写入方式反向读出 // 先将linkedlist的“容量”读出,然后将“所有的元素值”读出 private void readobject(java.io.objectinputstream s) throws java.io.ioexception, classnotfoundexception { // read in any hidden serialization magic s.defaultreadobject(); // 从输入流中读取“容量” int size = s.readint(); // 新建链表表头节点 header = new entry<e>(null, null, null); header.next = header.previous = header; // 从输入流中将“所有的元素值”并逐个添加到链表中 for (int i=; i<size; i++) addbefore((e)s.readobject(), header); } }
总结:
(01) linkedlist 实际上是通过双向链表去实现的。
它包含一个非常重要的内部类:entry。entry是双向链表节点所对应的数据结构,它包括的属性有:当前节点所包含的值,上一个节点,下一个节点。
(02) 从linkedlist的实现方式中可以发现,它不存在linkedlist容量不足的问题。
(03) linkedlist的克隆函数,即是将全部元素克隆到一个新的linkedlist对象中。
(04) linkedlist实现java.io.serializable。当写入到输出流时,先写入“容量”,再依次写入“每一个节点保护的值”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。
(05) 由于linkedlist实现了deque,而deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式:一种形式在操作失败时抛出异常,另一种形式返回一个特殊值(null 或 false,具体取决于操作)。
总结起来如下表格:
第一个元素(头部) 最后一个元素(尾部)
抛出异常 特殊值 抛出异常 特殊值
插入 addfirst(e) offerfirst(e) addlast(e) offerlast(e)
移除 removefirst() pollfirst() removelast() polllast()
检查 getfirst() peekfirst() getlast() peeklast()
(06) linkedlist可以作为fifo(先进先出)的队列,作为fifo的队列时,下表的方法等价:
队列方法 等效方法
add(e) addlast(e) offer(e) offerlast(e) remove() removefirst() poll() pollfirst() element() getfirst() peek() peekfirst()
(07) linkedlist可以作为lifo(后进先出)的栈,作为lifo的栈时,下表的方法等价:
栈方法 等效方法
push(e) addfirst(e)
pop() removefirst()
peek() peekfirst()
第4部分 linkedlist遍历方式
linkedlist遍历方式
linkedlist支持多种遍历方式。建议不要采用随机访问的方式去遍历linkedlist,而采用逐个遍历的方式。
(01) 第一种,通过迭代器遍历。即通过iterator去遍历。
for(iterator iter = list.iterator(); iter.hasnext();) iter.next();
(02) 通过快速随机访问遍历linkedlist
int size = list.size(); for (int i=0; i<size; i++) { list.get(i); }
(03) 通过另外一种for循环来遍历linkedlist
for (integer integ:list) ;
(04) 通过pollfirst()来遍历linkedlist
while(list.pollfirst() != null) ;
(05) 通过polllast()来遍历linkedlist
while(list.polllast() != null) ;
(06) 通过removefirst()来遍历linkedlist
try { while(list.removefirst() != null) ; } catch (nosuchelementexception e) { }
(07) 通过removelast()来遍历linkedlist
try { while(list.removelast() != null) ; } catch (nosuchelementexception e) { }
测试这些遍历方式效率的代码如下:
import java.util.list; import java.util.iterator; import java.util.linkedlist; import java.util.nosuchelementexception; /* * @desc 测试linkedlist的几种遍历方式和效率 * * */ public class linkedlistthrutest { public static void main(string[] args) { // 通过iterator遍历linkedlist iteratorlinkedlistthruiterator(getlinkedlist()) ; // 通过快速随机访问遍历linkedlist iteratorlinkedlistthruforeach(getlinkedlist()) ; // 通过for循环的变种来访问遍历linkedlist iteratorthroughfor(getlinkedlist()) ; // 通过pollfirst()遍历linkedlist iteratorthroughpollfirst(getlinkedlist()) ; // 通过polllast()遍历linkedlist iteratorthroughpolllast(getlinkedlist()) ; // 通过removefirst()遍历linkedlist iteratorthroughremovefirst(getlinkedlist()) ; // 通过removelast()遍历linkedlist iteratorthroughremovelast(getlinkedlist()) ; } private static linkedlist getlinkedlist() { linkedlist llist = new linkedlist(); for (int i=; i<; i++) llist.addlast(i); return llist; } /** * 通过快迭代器遍历linkedlist */ private static void iteratorlinkedlistthruiterator(linkedlist<integer> list) { if (list == null) return ; // 记录开始时间 long start = system.currenttimemillis(); for(iterator iter = list.iterator(); iter.hasnext();) iter.next(); // 记录结束时间 long end = system.currenttimemillis(); long interval = end - start; system.out.println("iteratorlinkedlistthruiterator:" + interval+" ms"); } /** * 通过快速随机访问遍历linkedlist */ private static void iteratorlinkedlistthruforeach(linkedlist<integer> list) { if (list == null) return ; // 记录开始时间 long start = system.currenttimemillis(); int size = list.size(); for (int i=; i<size; i++) { list.get(i); } // 记录结束时间 long end = system.currenttimemillis(); long interval = end - start; system.out.println("iteratorlinkedlistthruforeach:" + interval+" ms"); } /** * 通过另外一种for循环来遍历linkedlist */ private static void iteratorthroughfor(linkedlist<integer> list) { if (list == null) return ; // 记录开始时间 long start = system.currenttimemillis(); for (integer integ:list) ; // 记录结束时间 long end = system.currenttimemillis(); long interval = end - start; system.out.println("iteratorthroughfor:" + interval+" ms"); } /** * 通过pollfirst()来遍历linkedlist */ private static void iteratorthroughpollfirst(linkedlist<integer> list) { if (list == null) return ; // 记录开始时间 long start = system.currenttimemillis(); while(list.pollfirst() != null) ; // 记录结束时间 long end = system.currenttimemillis(); long interval = end - start; system.out.println("iteratorthroughpollfirst:" + interval+" ms"); } /** * 通过polllast()来遍历linkedlist */ private static void iteratorthroughpolllast(linkedlist<integer> list) { if (list == null) return ; // 记录开始时间 long start = system.currenttimemillis(); while(list.polllast() != null) ; // 记录结束时间 long end = system.currenttimemillis(); long interval = end - start; system.out.println("iteratorthroughpolllast:" + interval+" ms"); } /** * 通过removefirst()来遍历linkedlist */ private static void iteratorthroughremovefirst(linkedlist<integer> list) { if (list == null) return ; // 记录开始时间 long start = system.currenttimemillis(); try { while(list.removefirst() != null) ; } catch (nosuchelementexception e) { } // 记录结束时间 long end = system.currenttimemillis(); long interval = end - start; system.out.println("iteratorthroughremovefirst:" + interval+" ms"); } /** * 通过removelast()来遍历linkedlist */ private static void iteratorthroughremovelast(linkedlist<integer> list) { if (list == null) return ; // 记录开始时间 long start = system.currenttimemillis(); try { while(list.removelast() != null) ; } catch (nosuchelementexception e) { } // 记录结束时间 long end = system.currenttimemillis(); long interval = end - start; system.out.println("iteratorthroughremovelast:" + interval+" ms"); } }
执行结果:
iteratorlinkedlistthruiterator:8 ms iteratorlinkedlistthruforeach:3724 ms iteratorthroughfor2:5 ms iteratorthroughpollfirst:8 ms iteratorthroughpolllast:6 ms iteratorthroughremovefirst:2 ms iteratorthroughremovelast:2 ms
由此可见,遍历linkedlist时,使用removefist()或removelast()效率最高。但用它们遍历时,会删除原始数据;若单纯只读取,而不删除,应该使用第3种遍历方式。
无论如何,千万不要通过随机访问去遍历linkedlist!
第5部分 linkedlist示例
下面通过一个示例来学习如何使用linkedlist的常用api
import java.util.list; import java.util.iterator; import java.util.linkedlist; import java.util.nosuchelementexception; /* * @desc linkedlist测试程序。 * * * */ public class linkedlisttest { public static void main(string[] args) { // 测试linkedlist的api testlinkedlistapis() ; // 将linkedlist当作 lifo(后进先出)的堆栈 uselinkedlistaslifo(); // 将linkedlist当作 fifo(先进先出)的队列 uselinkedlistasfifo(); } /* * 测试linkedlist中部分api */ private static void testlinkedlistapis() { string val = null; //linkedlist llist; //llist.offer("10"); // 新建一个linkedlist linkedlist llist = new linkedlist(); //---- 添加操作 ---- // 依次添加1,2,3 llist.add("1"); llist.add("2"); llist.add("3"); // 将“4”添加到第一个位置 llist.add(1, "4"); system.out.println("\ntest \"addfirst(), removefirst(), getfirst()\""); // (01) 将“10”添加到第一个位置。 失败的话,抛出异常! llist.addfirst("10"); system.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话,抛出异常! system.out.println("llist.removefirst():"+llist.removefirst()); system.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话,抛出异常! system.out.println("llist.getfirst():"+llist.getfirst()); system.out.println("\ntest \"offerfirst(), pollfirst(), peekfirst()\""); // (01) 将“10”添加到第一个位置。 返回true。 llist.offerfirst("10"); system.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话,返回null。 system.out.println("llist.pollfirst():"+llist.pollfirst()); system.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话,返回null。 system.out.println("llist.peekfirst():"+llist.peekfirst()); system.out.println("\ntest \"addlast(), removelast(), getlast()\""); // (01) 将“20”添加到最后一个位置。 失败的话,抛出异常! llist.addlast("20"); system.out.println("llist:"+llist); // (02) 将最后一个元素删除。 失败的话,抛出异常! system.out.println("llist.removelast():"+llist.removelast()); system.out.println("llist:"+llist); // (03) 获取最后一个元素。 失败的话,抛出异常! system.out.println("llist.getlast():"+llist.getlast()); system.out.println("\ntest \"offerlast(), polllast(), peeklast()\""); // (01) 将“20”添加到第一个位置。 返回true。 llist.offerlast("20"); system.out.println("llist:"+llist); // (02) 将第一个元素删除。 失败的话,返回null。 system.out.println("llist.polllast():"+llist.polllast()); system.out.println("llist:"+llist); // (03) 获取第一个元素。 失败的话,返回null。 system.out.println("llist.peeklast():"+llist.peeklast()); // 将第3个元素设置300。不建议在linkedlist中使用此操作,因为效率低! llist.set(2, "300"); // 获取第3个元素。不建议在linkedlist中使用此操作,因为效率低! system.out.println("\nget(3):"+llist.get(2)); // ---- toarray(t[] a) ---- // 将linkedlist转行为数组 string[] arr = (string[])llist.toarray(new string[]); for (string str:arr) system.out.println("str:"+str); // 输出大小 system.out.println("size:"+llist.size()); // 清空linkedlist llist.clear(); // 判断linkedlist是否为空 system.out.println("isempty():"+llist.isempty()+"\n"); } /** * 将linkedlist当作 lifo(后进先出)的堆栈 */ private static void uselinkedlistaslifo() { system.out.println("\nuselinkedlistaslifo"); // 新建一个linkedlist linkedlist stack = new linkedlist(); // 将1,2,3,4添加到堆栈中 stack.push("1"); stack.push("2"); stack.push("3"); stack.push("4"); // 打印“栈” system.out.println("stack:"+stack); // 删除“栈顶元素” system.out.println("stack.pop():"+stack.pop()); // 取出“栈顶元素” system.out.println("stack.peek():"+stack.peek()); // 打印“栈” system.out.println("stack:"+stack); } /** * 将linkedlist当作 fifo(先进先出)的队列 */ private static void uselinkedlistasfifo() { system.out.println("\nuselinkedlistasfifo"); // 新建一个linkedlist linkedlist queue = new linkedlist(); // 将10,20,30,40添加到队列。每次都是插入到末尾 queue.add("10"); queue.add("20"); queue.add("30"); queue.add("40"); // 打印“队列” system.out.println("queue:"+queue); // 删除(队列的第一个元素) system.out.println("queue.remove():"+queue.remove()); // 读取(队列的第一个元素) system.out.println("queue.element():"+queue.element()); // 打印“队列” system.out.println("queue:"+queue); } }
运行结果:
test "addfirst(), removefirst(), getfirst()" llist:[10, 1, 4, 2, 3] llist.removefirst():10 llist:[1, 4, 2, 3] llist.getfirst():1 test "offerfirst(), pollfirst(), peekfirst()" llist:[10, 1, 4, 2, 3] llist.pollfirst():10 llist:[1, 4, 2, 3] llist.peekfirst():1 test "addlast(), removelast(), getlast()" llist:[1, 4, 2, 3, 20] llist.removelast():20 llist:[1, 4, 2, 3] llist.getlast():3 test "offerlast(), polllast(), peeklast()" llist:[1, 4, 2, 3, 20] llist.polllast():20 llist:[1, 4, 2, 3] llist.peeklast():3 get(3):300 str:1 str:4 str:300 str:3 size:4 isempty():true uselinkedlistaslifo stack:[4, 3, 2, 1] stack.pop():4 stack.peek():3 stack:[3, 2, 1] uselinkedlistasfifo queue:[10, 20, 30, 40] queue.remove():10 queue.element():20 queue:[20, 30, 40]
以上所述是小编给大家介绍的java中linkedlist详解和使用示例,希望对大家有所帮助
推荐阅读
-
Java中LinkedList详解和使用示例_动力节点Java学院整理
-
ObjectInputStream 和 ObjectOutputStream 介绍_动力节点Java学院整理
-
Struts1和struts2的区别_动力节点Java学院整理
-
Struts1简介和入门_动力节点Java学院整理
-
struts1登录示例代码_动力节点Java学院整理
-
TreeSet详解和使用示例_动力节点Java学院整理
-
Java中ArrayList和LinkedList之间的区别_动力节点Java学院整理
-
详解PipedInputStream和PipedOutputStream_动力节点Java学院整理
-
Java中Object toString方法简介_动力节点Java学院整理
-
Java中List Set和Map之间的区别_动力节点Java学院整理