概述
集合java.util.LinkedList存储的结构是 链表 结构。
特点： 插入 和 移除 元素比较快
常用方法
实际开发中对一个集合元素的添加与删除经常涉及到首尾操作，而LinkedList提供了大量首尾操作的方法。这些方法我们作为了解即可：
public void addFirst(E e):将指定元素插入此列表的开头。public void addLast(E e):将指定元素添加到此列表的结尾。public E getFirst():返回此列表的第一个元素。public E getLast():返回此列表的最后一个元素。public E removeFirst():移除并返回此列表的第一个元素。public E removeLast():移除并返回此列表的最后一个元素。public E pop():从此列表所表示的堆栈处弹出一个元素。public void push(E e):将元素推入此列表所表示的堆栈。public boolean isEmpty()：如果列表不包含元素，则返回true。
LinkedList实现了 List接口，List中的方法LinkedList都可以使用，这里就不做详细介绍
例子：
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> link = new LinkedList<String>();
//添加元素
link.addFirst("abc1");
link.addFirst("abc2");
link.addFirst("abc3");
System.out.println(link);
// 获取元素
System.out.println(link.getFirst());
System.out.println(link.getLast());
// 删除元素
System.out.println(link.removeFirst());
System.out.println(link.removeLast());
while (!link.isEmpty()) { //判断集合是否为空
System.out.println(link.pop()); //弹出集合中的栈顶元素
}
System.out.println(link);
}
}
实现原理
在早期的 java 版本中LinkedList用的是双向链表
public class MyLinkedList {
// 集合中元素的真实数量
private int size;
private Node first;
private Node last;
/**
* 新增
* 1、如果是第一次添加元素，那么first是null的，所以要创建以Node赋值给first，此时链表中只有一个元素，那么最后一个元素last和first就是同一个对象
* 2、从第二次开始添加元素时，只需要创建一个新的Node，让它的上一个指针指向last，last的下一个指针指向Node
* 3、新增的元素一定是最后一个元素，所有给last赋值成最后一个元素
* 4、size++
* @param obj
* 新增的元素
*/
public void add(Object obj) {
if(first == null){
first = new Node(null, obj, null);
last = first;
}else{
Node node = new Node(last, obj, null);
last.next = node;
last = node;
}
size++;
}
public void add(int index, Object obj) {
Node nodeNext = getNode(index);
Node nodePrev = nodeNext.prev;
Node node = new Node(nodePrev, obj, nodeNext);
nodePrev.next = node;
nodeNext.prev = node;
size++;
}
/**
* 返回集合的长度
* @return size
*/
public int size() {
return size;
}
/**
* 返回集合的数组
* 1、size==0，代表集合中没有元素，返回一个长度为0的数组
* 2、当index==0时，代表第一个元素，直接赋值
* 3、node是当前元素，赋值之后，要让node=node.next，代表当前元素要向后指向
* @return 数组
*/
public Object[] toArray() {
if(size == 0){
return new Object[0];
}
Object[] result = new Object[size];
int index = 0;
Node node = first.next;
while(true){
if(index == 0){
result[index++] = first.element;
}
if(node == null){
break;
}
result[index++] = node.element;
node = node.next;
}
return result;
}
/**
* 通过索引值获取元素
* 调用了getNode方法，获取了index的Node对象，返回他的element值
* @param index 索引
* @return 元素
*/
public Object get(int index) {
return getNode(index).element;
}
/**
* 通过索引获取Node对象
* @param index 索引
* @return Node对象
*/
private Node getNode(int index) {
if(index == 0){
return first;
}
Node node = first;
for(int i = 0; i < index; i++){
node = node.next;
}
return node;
}
private class Node{
Object element;
Node next;
Node prev;
public Node(Node prev, Object element, Node next){
this.element = element;
this.prev = prev;
this.next = next;
}
}
}