首页 > 代码库 > Java集合02----LinkedList的遍历方式及应用

Java集合02----LinkedList的遍历方式及应用

2024-07-07 11:08:26   227人阅读

                                          Java集合02----LinkedList的遍历方式及应用

     前面已经学习了ArrayList的源码，为了学以致用，故列举一些ArrayList的遍历方式及应用。JDK源码学习系列05----LinkedList

1.LinkedList的遍历方式

a.一般的for循环(随机访问)

int size = list.size();
for (int i=0; i<size; i++) {
    list.get(i);        
}

b.for--each循环

for (Integer integ:list) 
    ;
c.迭代器iterator

for(Iterator iter = list.iterator(); iter.hasNext();)
    iter.next();
d.用pollFirst()来遍历LinkedList

while(list.pollFirst() != null)
    ;
e.用pollLast()来遍历LinkedList

while(list.pollLast() != null)
    ;
f.用removeFirst()来遍历LinkedList

try {
    while(list.removeFirst() != null)
        ;
} catch (NoSuchElementException e) {
}
g.用removeLast()来遍历LinkedList

try {
    while(list.removeLast() != null)
        ;
} catch (NoSuchElementException e) {
}

LinkedList遍历效率分析：

package com.sheepmu;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/*
 * @author SheepMu
 */
public class LinkedListTest {
    public static void main(String[] args) {
    	LinkedList<Integer> llist = new LinkedList<Integer>();
        for (int i=0; i<100000; i++)
            llist.addLast(i);
        
        byCommonFor(llist) ;// 通过一般for循环来遍历LinkedList
        byForEach(llist) ;  // 通过for-each来遍历LinkedList
        byIterator(llist) ; // 通过Iterator来遍历LinkedList
        byPollFirst(llist) ;    // 通过PollFirst()遍历LinkedList   
        byPollLast(llist) ; // 通过PollLast()遍历LinkedList 
        byRemoveFirst(llist) ;   // 通过removeFirst()遍历LinkedList   
        byRemoveLast(llist) ; // 通过removeLast()遍历LinkedList
    }
    
 
    private static void byCommonFor(LinkedList<Integer> list) {// 通过一般for循环来遍历LinkedList
        if (list == null)
            return ;
        long start = System.currentTimeMillis();     
        int size = list.size();
        for (int i=0; i<size; i++) {
            list.get(i);        
        }
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byCommonFor------->" + total+" ms");
    }
    
    private static void byForEach(LinkedList<Integer> list) {// 通过for-each来遍历LinkedList
        if (list == null)
            return ; 
        long start = System.currentTimeMillis();       
        for (Integer integ:list) 
            ; 
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byForEach------->" + total+" ms");
    }
 
    private static void byIterator(LinkedList<Integer> list) {// 通过Iterator来遍历LinkedList
        if (list == null)
            return ; 
        long start = System.currentTimeMillis();     
        for(Iterator iter = list.iterator(); iter.hasNext();)
            iter.next(); 
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byIterator------->" + total+" ms");
    }
 
    private static void byPollFirst(LinkedList<Integer> list) {//通过PollFirst()遍历LinkedList   
        if (list == null)
            return ; 
        long start = System.currentTimeMillis();
        while(list.pollFirst() != null)
            ; 
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byPollFirst------->" + total+" ms");
    }
 
    private static void byPollLast(LinkedList<Integer> list) {// 通过PollLast()遍历LinkedList 
        if (list == null)
            return ; 
        long start = System.currentTimeMillis();
        while(list.pollLast() != null)
            ; 
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byPollLast------->" + total+" ms");
    }
 
    private static void byRemoveFirst(LinkedList<Integer> list) {// 通过removeFirst()遍历LinkedList
        if (list == null)
            return ; 
        long start = System.currentTimeMillis();
        try {
            while(list.removeFirst() != null)
                ;
        } catch (NoSuchElementException e) {
        } 
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byRemoveFirst------->" + total+" ms");
    }
 
    private static void byRemoveLast(LinkedList<Integer> list) {// 通过removeLast()遍历LinkedList
        if (list == null)
            return ;
        long start = System.currentTimeMillis();
        try {
            while(list.removeLast() != null)
                ;
        } catch (NoSuchElementException e) {
        }
        long end = System.currentTimeMillis();
        long total = end - start;
        System.out.println("byRemoveLast------->" + total+" ms");
    }

}
byCommonFor------->5342 ms
byForEach------->11 ms
byIterator------->8 ms
byPollFirst------->4 ms
byPollLast------->0 ms
byRemoveFirst------->0 ms
byRemoveLast------->0 ms
由此可见，遍历LinkedList时，使用removeFist()或removeLast()效率最高。但用它们遍历时，会删除原始数据；若单纯只读取，而不删除，LinkedList遍历时建议使用For-each或者迭代器的方式。千万不要通过随机访问去遍历LinkedList！


2.LinkedList应用举例

a.LinkedList常用方法举例

package com.sheepmu; 
import java.util.LinkedList; 
/* 
 * @author SheepMu
 */
public class LinkedListTest {
    public static void main(String[] args) {   
    	commonMethods() ; // 测试LinkedList的常用方法 
    	likeStack();// 将LinkedList当作 LIFO(后进先出)的堆栈 
    	likeQueue(); // 将LinkedList当作 FIFO(先进先出)的队列
    }
  
    private static void commonMethods() {      
        LinkedList<String> llist = new LinkedList<String>();      
        llist.add("A");//添加元素
        llist.add("B");
        llist.add("C");
        llist.add("D");
        System.out.println("llist------->"+llist);
        llist.add(1, "E");// 将“E”添加到第索引为1的个位置
        System.out.println("添加E到索引为1的个位置后的llist------->"+llist);
      
        llist.addFirst("X");//  将“X”添加到第一个位置。  失败的话，抛出异常！
        System.out.println("在最前面添加X后的llist------->"+llist); 
        System.out.println("删除第一个元素并获得并返回被删除元素----->"+llist.removeFirst());  // 将第一个元素删除。 
        System.out.println("删除第一个元素后的llist------->"+llist); 
              
        llist.offerFirst("Y");// 将“Y”添加到第一个位置。  返回true。
        System.out.println("将Y添加到第一个位置后的llist------->"+llist);    
        System.out.println("删除第一个元素并获得并返回被删除元素------>"+llist.pollFirst()); // 将第一个元素删除。 
        System.out.println("将第一个元素删除后的llist------->"+llist);  
        llist.removeLast() ;
        System.out.println("移除最后一个元素后的llist------->"+llist); 
           
        llist.offerLast("Z"); //   将“Z”添加到最后一个位置 
        System.out.println("在最后添加Z后的llist------->"+llist);  
        llist.set(2, "M");// 将第3个元素设置M。 
        System.out.println("将第3个元素设置M后的llist------->"+llist); 
        System.out.println("size:"+llist.size());// LinkedList大小       
        llist.clear();// 清空LinkedList 
    }

    
    private static void likeStack() { //将LinkedList作为栈使用!!!!!!!!!!!!     
        LinkedList<String> stack = new LinkedList<String>();
        stack.push("A");//向栈中添加元素
        stack.push("B");
        stack.push("C");
        stack.push("D");
        System.out.println("stack--------->"+stack);
        stack.pop() ;// 删除“栈顶元素”
        System.out.println("删除栈顶后的stack--------->"+stack);      
        System.out.println("栈顶元素--------->"+stack.peek()); // 取出栈顶
 
    }
 
    private static void likeQueue() {//将LinkedList作为队列使用!!!!!!!!!!!!       
        LinkedList<String> queue = new LinkedList<String>();
        queue.add("A");//向队列中添加元素
        queue.add("B");
        queue.add("C");
        queue.add("D");    
        System.out.println("queue--------->"+queue);
        queue.remove() ;//删除队列的第一个元素
        System.out.println("删除队列的第一个元素后queue--------->"+queue);       
        System.out.println("队列第一个元素------->"+queue.element()); // 读取队列的第一个元素 
  
    }
}
llist------->[A, B, C, D]
添加E到索引为1的个位置后的llist------->[A, E, B, C, D]
在最前面添加X后的llist------->[X, A, E, B, C, D]
删除第一个元素并获得并返回被删除元素----->X
删除第一个元素后的llist------->[A, E, B, C, D]
将Y添加到第一个位置后的llist------->[Y, A, E, B, C, D]
删除第一个元素并获得并返回被删除元素------>Y
将第一个元素删除后的llist------->[A, E, B, C, D]
移除最后一个元素后的llist------->[A, E, B, C]
在最后添加Z后的llist------->[A, E, B, C, Z]
将第3个元素设置M后的llist------->[A, E, M, C, Z]
size:5
stack--------->[D, C, B, A]
删除栈顶后的stack--------->[C, B, A]
栈顶元素--------->C
queue--------->[A, B, C, D]
删除队列的第一个元素后queue--------->[B, C, D]
队列第一个元素------->B


联系
我们