TIJ学习笔记之LinkedList

旧城等待， 2022-08-11 16:56 205阅读 0赞

LinkedList是实现List接口的类之一，它相比于ArrayList更适合删除与插入，而不适合随机访问。是因为的它的实现数据结构是双向链表。

根据数据结构的知识可知，LinkedList确实较适合删除与插入。

下面是一些它的常用方法：

package com.zhiru;
    
    import java.util.LinkedList;
    
    public class LinkedListTests {
    
    	public static void prt(String s){
    		System.out.print(s+"\n");
    	}
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		/*
    		 * (1) 泛型是没有数组的。编译器不承认 HashMap<K,V>[]这种形式的： 
          Cannot create a generic array of HashMap<k,v> 
        原因就是数组必须确定他每一个元素的类型。但是泛型在编译阶段有一个类型擦除的问题，
        也就是说编译器理解HashMap<Integer,Integer>和HashMap<String,String>都是同一种类型HashMap。
        如果泛型数组存在，那么HashMap<Integer,Integer>和HashMap<String,String>
        对象都可以加入到同一个HashMap[]数组中，这会造成灾难性的结果。 
    		 */
    		LinkedList<String> list=new LinkedList<String>();
    		for(int i=0;i<10;i++){
    			list.add(String.valueOf(i+1));
    		}
    		prt(""+list);
    		prt("getFirst:"+list.getFirst());
    		prt("getLast:"+list.getLast());
    		prt("peek:"+list.peek());
    		prt("remove:"+list.remove());
    		prt("removeFirst:"+list.removeFirst());
    		prt("removeLast:"+list.removeLast());
    		prt("poll:"+list.poll());
    		prt(""+list);
    		list.addFirst("10000000");
    		prt("After add First 10000000:"+list.getFirst());
    		list.offer("xx123xx");
    		prt("after add the tail elements xx123xx:"+list.getLast());
    		list.addLast("WaHAGA");
    		prt("after added the WaHAGA as the last elememts:"+list);
    		prt("removeLast:"+list.removeLast());
    		prt("all list"+list);
    		MyQueue<String> q=new MyQueue<String>();
    		q.enQueue("1");
    		q.enQueue("2");
    		q.enQueue("3");
    		prt(""+q);
    		prt("获取队头元素："+q.getFront());
    		prt("出队:"+q.deQueue());
    		prt(""+q);
    		
    	}
    }

\[1, 2, 3, 4, 5, 6, 7, 8, 9, 10\]  
getFirst:1  
getLast:10  
peek:1  
remove:1  
removeFirst:2  
removeLast:10  
poll:3  
\[4, 5, 6, 7, 8, 9\]  
After add First 10000000:10000000  
after add the tail elements xx123xx:xx123xx  
after added the WaHAGA as the last elememts:\[10000000, 4, 5, 6, 7, 8, 9, xx123xx, WaHAGA\]  
removeLast:WaHAGA  
all list\[10000000, 4, 5, 6, 7, 8, 9, xx123xx\]

用linkedList实现栈

package com.zhiru;
    
    import java.util.LinkedList;
    /*
     * 用LinkedList实现一个栈
     * lifo
     */
    public class MyStack<E> {
    	private LinkedList<E> s = new LinkedList<E>();
    	public void push(E e){
    		s.addFirst(e);
    	}
    	//peek方法提供栈顶元素，但不删除它
    	public E peek(){
    		return s.getFirst();
    	}
    	//pop方法删除并返回栈顶元素.
    	public E pop(){
    		return s.removeFirst();
    	}
    	public boolean empty(){
    		return s.isEmpty();
    	}
    	public String toString(){
    		return s.toString();
    	}
    }

再实现一个队列：

package com.zhiru;
    import java.util.LinkedList;
    //用LinkedList实现队列.
    
    //fifo
    public class MyQueue<E> {
    	private LinkedList<E> s = new LinkedList<E>();
    	public void enQueue(E e){
    		s.offer(e);
    	}
    	public E deQueue(){
    		return s.poll();
    	}
    	public E getFront(){
    		return s.peek();
    	}
    	public boolean isEmpty(){
    		return s.isEmpty();
    	}
    	public int size(){
    		return s.size();
    	}
    	public String toString(){
    		return s.toString();
    	}
    }