与ArrayList一样,LinkedList也实现了List接口,诸如add,remove,contains等等方法。
以双向链表
实现。链表无容量限制,但双向链表本身使用了更多空间,也需要额外的链表指针操作。
按下标访问元素–get(i)/set(i,e) 要悲剧的遍历链表将指针移动到位(如果i>数组大小的一半,会从末尾移起)。
插入、删除元素时修改前后节点的指针即可,但还是要遍历部分链表的指针才能移动到下标所指的位置,只有在链表两头的操作–add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指针的移动。
LinkedList 实现了:List
、Deque
(双向链表结构)、Queue
(队列接口)。
1、Deque
LinkedList <xxx> ll = new LinkedList<xxx>();
ll.addFirst("q0"); //头部加入
ll.addLast("q1"); // 尾部加入
System.out.println(ll.getFirst()); //查看最前面的对象
System.out.println(ll.getLast()); //查看最后面的对象
System.out.println(ll.removeFirst()); // 删除第一个对象
System.out.println(ll.removeLast()); // 删除最后一个对象
System.out.println(ll); // 取出会导致对象被删除
2、Queue
Queue是在两端出入的List,所以也可以用数组或链表来实现。
队列:先进先出FIFOoffer
在最后添加元素poll
取出第一个元素peek
查看第一个元素LinkedList
:以双向链表实现的LinkedList既是List,也是Queue。它是唯一一个允许放入null的Queue。Queue<Hero> q= new LinkedList<Hero>();
还有很多Quene,比如ArrayDeque
、PriorityQueue
。。。
3、ArrayList 和 LinkedList 的区别
ArrayList
- 插入/删除数据速度慢。因为要把插入点后所有对象移位。
- 顺序结构,可直接定位到某个位置的对象,定位速度快。
LinkedList
- 插入,删除数据快。只要断开插入点的连接,重新连接到别的块就OK。
- 链表结构,不可以直接定位到某个位置的对象,必须根据链表的方向一个一个找,定位速度慢。
public class TestCollection {
public static void main(String[] args) {
List<Integer> l1 = new ArrayList<>();
List<Integer> l2 = new LinkedList<>();
insertFirst(l1,"ArrayList");
insertFirst(l2,"LinkedList");
}
private static void insertFirst(List<Integer> l, String type) {
int total = 1000 * 100;
final int number = 5;
long start = System.currentTimeMillis();
for (int i = 0; i < total; i++) {
l.add(0, number);
}
long end = System.currentTimeMillis();
System.out.printf("在%s 最前面插入%d条数据,总共耗时 %d 毫秒 %n", type, total, end - start);
}
}
在ArrayList 最前面插入100000条数据,总共耗时 1006 毫秒
在LinkedList 最前面插入100000条数据,总共耗时 4 毫秒
4、练习
练习-使用LinkedList实现Stack栈
与FIFO(先入先出的)队列类似的一种数据结构是FILO先入后出栈Stack
根据接口Stack :
实现类:MyStack
public class MyStack implements Stack
并向这个栈中,压入5个英雄,接着弹出5个英雄
package collection;
import charactor.Hero;
public interface Stack {
//把英雄推入到最后位置
public void push(Hero h);
//把最后一个英雄取出来
public Hero pull();
//查看最后一个英雄
public Hero peek();
}
package collection;
import java.util.LinkedList;
import java.util.List;
public class MyStack implements Stack{
LinkedList<Hero> heros = new LinkedList<>();
@Override
//把英雄推入到最后位置
public void push(Hero h) {
heros.addLast(h);
}
@Override
public Hero pull() {
// TODO Auto-generated method stub
Hero h = heros.removeLast();
return h;
}
@Override
public Hero peek() {
// TODO Auto-generated method stub
Hero h = heros.getLast();
return h;
}
}