一、简介
- LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
- LinkedList 实现 List 接口，能进行队列操作。
- LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
- ArrayList底层是由数组支持，而LinkedList 是由双向链表实现的，其中的每个对象包含数据的同时还包含指向链表中前一个与后一个元素的引用。
二、构造函数
- LinkedList(): 生成空的链表
- LinkedList(Collection C): 根据一个集合创建一个链表。
三、常用方法
1、增加：
- boolean add(E e)：在链表后添加一个元素；
- void add(int index, E element)：在指定位置插入一个元素；
- void addFirst(E e)：在链表头部插入一个元素；
- void addLast(E e)：在链表尾部添加一个元素；
- void push(E e)：与addFirst方法一致；
- boolean offer(E e)：在链表尾部插入一个元素 ；
- boolean offerFirst(E e)：在头部添加；
- boolean offerLast(E e)：在尾部添加。
2、删除：
- Object remove() ：移除链表中第一个元素;
- boolean remove(E e)：移除指定元素；
- Object removeFirst(E e)：删除头，获取元素并删除；
- Object removeLast(E e)：删除尾；
- Object poll()：查询并移除第一个元素。
- Object pollFirst()：删除头；
- Object pollLast()：删除尾；
- Object pop()：和removeFirst方法一致，删除头；
3、查：
- Object get(int index)：按照下标获取元素；
- Object getFirst()：获取第一个元素；
- Object getLast()：获取最后一个元素；
- Object peek()：获取第一个元素，但是不移除；
- Object peekFirst()：获取第一个元素，但是不移除；
- Object peekLast()：获取最后一个元素，但是不移除；
一个例子：
public class LinkedListDemo {
public static void main(String[] srgs) {
LinkedList linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(1, 2);
linkedList.addFirst(0);
linkedList.addLast(3);
linkedList.push(-1);
linkedList.offer(4);
linkedList.offerFirst(-2);
linkedList.offerLast(5);
System.out.println("LinkedList: " + linkedList);
linkedList.remove();
System.out.println("removeFirst(): " + linkedList.removeFirst());
System.out.println("removeLast(): " + linkedList.removeLast());
System.out.println("After remove:" + linkedList);
linkedList.poll();
linkedList.pollFirst();
linkedList.pollLast();
System.out.println("After poll():" + linkedList);
linkedList.pop();
System.out.println("After pop():" + linkedList);
linkedList.add(4);
linkedList.add(5);
System.out.println("get():" + linkedList.get(1));
System.out.println("getFirst(): " + linkedList.getFirst());
System.out.println("getLast(): " + linkedList.getLast());
System.out.println("peek(): " + linkedList.peek());
System.out.println("peekFirst(): " + linkedList.peekFirst());
System.out.println("peekLast(): " + linkedList.peekLast());
}
}
输出结果：
LinkedList: [-2, -1, 0, 1, 2, 3, 4, 5]
removeFirst(): -1
removeLast(): 5
After remove:[0, 1, 2, 3, 4]
After poll():[2, 3]
After pop():[3]
get():4
getFirst(): 3
getLast(): 5
peek(): 3
peekFirst(): 3
peekLast(): 5
4、其他
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] srgs) {
LinkedList linkedList = new LinkedList();
linkedList.add(3);
linkedList.add(4);
linkedList.add(5);
// 判断此列表包含指定元素，如果是，则返回true
System.out.println("contains(1) is :" + linkedList.contains(1));
// 获取但不移除此列表的头
System.out.println("element(): " + linkedList.element());
// 返回此列表的元素个数
System.out.println("size is : " + linkedList.size());
// 将此列表中指定位置的元素替换为指定的元素
linkedList.set(1, 3);
System.out.println("After set(1, 3):" + linkedList);
// 返回此列表中首次出现的指定元素的索引
System.out.println("indexOf(3): " + linkedList.indexOf(3));
// 返回此列表中最后出现的指定元素的索引
System.out.println("lastIndexOf(3): " + linkedList.lastIndexOf(3));
System.out.println("subList(2,3): " + linkedList.subList(2,3));
}
}
输出结果：
contains(1) is :false
element(): 3
size is : 3
After set(1, 3):[3, 3, 5]
indexOf(3): 0
lastIndexOf(3): 1
subList(2,3): [5]
四、遍历
1、迭代器遍历
Iterator<Integer> iterator = linkedList.iterator();
while(iterator.hasNext()){
iterator.next();
2、for循环get()遍历
for(int i = 0; i < linkedList.size(); i++){
linkedList.get(i);
}
3、Foreach循环遍历
for(Integer i : linkedList) {
// some code
};
4、通过pollFirst()或pollLast()遍历
while(linkedList.size() != 0){
linkedList.pollFirst();
}
5、通过removeFirst()或removeLast()遍历
while(linkedList.size() != 0){
linkedList.removeFirst();
}
注意：
- 遍历LinkedList时，使用removeFirst()或removeLast()效率最高，而for循环get()效率最低，应避免使用这种方式进行。
- 使用pollFirst()或pollLast()或removeFirst()或removeLast()遍历时，会删除原始数据，若只单纯的读取，应当选用第一种或第三种方式。
import java.util.Iterator;
import java.util.LinkedList;
public class LinkedListLoop {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
for(int i = 0; i < 3; i++){
linkedList.add(i);
}
// 迭代器遍历
Iterator<Integer> iterator = linkedList.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());;
}
// 顺序遍历(随机遍历)
for(int i = 0; i < linkedList.size(); i++){
System.out.println(linkedList.get(i));
}
// 另一种for循环遍历
for(Integer i : linkedList) {
System.out.println(i);
};
// 通过pollFirst()或pollLast()来遍历LinkedList
LinkedList<Integer> temp1 = new LinkedList<>();
temp1.addAll(linkedList);
while(temp1.size() != 0){
System.out.println(temp1.pollFirst());
}
// 通过removeFirst()或removeLast()来遍历LinkedList
LinkedList<Integer> temp2 = new LinkedList<>();
temp2.addAll(linkedList);
while(temp2.size() != 0){
System.out.println(temp2.removeFirst());
}
}
}
