Java常用API之LinkedList类解读

写在开头：本文用于作者学习我将官方文档中LinkedList 1.6版本中类中绝大部分API全测了一遍并打印了结果，日拱一卒，常看常新。

自己补充了一些对该数据结构的理解，如有不对的地方，请各位指正，谢谢。

首先，LinkedList是一个链表结构，往它里面添加数据的时候，它会自动帮你记录每个元素的位置，记载它的nex（指针）t里面。

相比数组而言，它就像一个有很多节的火车（装载量可变），数组有点像货车（装载量不可变），可以通过如下代码定义一个简单的链表结构

补充：定义单向链表的节点类

class ListNode {//定义链表结构，属性一int value记录值（载重），ListNode next记录下一节点（车厢）的位置int val;//数据域ListNode next;//指针域， next表示指针，表示下一个节点是谁
}

它里面有两个属性要被定义，一个是数据域，用来存链表中的数据；一个是指针域，用来指向它下一个节点的内存地址。

先定义双向链表的节点类

public class Node {//定义节点类int data;Node prev;//指向前一个位置Node next;//后一个位置public Node(int data) {//构造函数this.data = data;this.prev = null;this.next = null;}
}

再定义个双向链表类

public class DoublyLinkedList {Node head;//head变量类型为Node类，前面定义节点类就为了这，用于存储链表头节点的引用public DoublyLinkedList() {this.head = null;}// 添加元素到链表末尾public void add(int data) {Node newNode = new Node(data);if (head == null) {head = newNode;// 如果链表为空，新节点成为头节点} else {//如果链表不为空Node current = head;// 将头节点先赋给当前节点while (current.next != null) {//再判断当前节点的下一个索引是否为空，不为空继续遍历current = current.next;//直到当前节点的下个索引指向空，退出循环}current.next = newNode;//将当前节点索引指向新节点newNode.prev = current;//将新节点的上一个索引指向当前节点}}// 删除指定元素public void remove(int data) {if (head == null) return;Node current = head;while (current != null) {if (current.data == data) {if (current.prev != null) {current.prev.next = current.next;} else {head = current.next;}if (current.next != null) {current.next.prev = current.prev;}return;}current = current.next;}}// 打印链表public void printList() {Node current = head;while (current != null) {System.out.print(current.data + " ");current = current.next;}System.out.println();}public static void main(String[] args) {DoublyLinkedList dll = new DoublyLinkedList();dll.add(10);dll.add(20);dll.add(30);dll.printList();  // 打印: 10 20 30dll.remove(20);dll.printList();  // 打印: 10 30}
}

下面是一些它的方法：

add() 末尾添加元素

@Testpublic void test_add(){// 将指定元素添加到此列表的结尾LinkedList<Character> a = new LinkedList<Character>() {{add('a');}};System.out.println(a);//[a]}

addIndex() 指定索引添加元素

@Testpublic void test_addIndex(){//在此列表中指定的位置插入指定的元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');add(0,'b');}};System.out.println(a);//[b, a]}

addAll() 往里加一个集合

@Testpublic void test_addAll(){// 添加指定 collection 中的所有元素到此列表的结尾，顺序是指定 collection 的迭代器返回这些元素的顺序LinkedList<Character> b = new LinkedList<Character>() {{add('^');}};LinkedList<Character> a = new LinkedList<Character>() {{add('a');add(0,'b');addAll(b);}};System.out.println(a);//[b, a, ^]}

addFirst() 头位置添加

@Testpublic void test_addFirst(){//将指定元素插入此列表的开头LinkedList<Character> a = new LinkedList<Character>() {{add('a');addFirst('c');}};System.out.println(a);//[c, a]}

addLast() 末尾添加

@Testpublic void test_addLast(){//将指定元素添加到此列表的结尾LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};System.out.println(a);//[a, d]}

clear()

@Testpublic void test_clear(){//从此列表中移除所有元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};a.clear();System.out.println(a);//[]}

clone()

@Testpublic void test_clone(){//返回此 LinkedList 的浅表副本LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Object clone = a.clone();System.out.println(clone);//[a, d]}

contains() 是否包含

@Testpublic void test_contains(){//如果此列表包含指定元素，则返回 trueLinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};boolean a1 = a.contains('a');System.out.println(a1);//true}

element() 获取但不移除头元素

@Testpublic void test_element(){//获取但不移除此列表的头（第一个元素）。LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Character element = a.element();System.out.println(element);//aSystem.out.println(a);//[a, d]}

get() 按索引取值

@Testpublic void test_get(){//获取但不移除此列表的头（第一个元素）。LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Character character = a.get(1);System.out.println(character);//d}

getFirst()

@Testpublic void test_getFirst(){//获取但不移除此列表的头（第一个元素）。LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Character first = a.getFirst();System.out.println(first);//a}

getLast()

@Testpublic void test_getLast(){//获取但不移除此列表的头（第一个元素）。LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Character last = a.getLast();System.out.println(last);//d}

indexOf() 按值取索引

@Testpublic void test_indexOf(){//返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};int index = a.indexOf('a');System.out.println(index);//0}

lastIndexOf() 最后位置出现的索引

@Testpublic void test_lastIndexOf(){//返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};int index = a.lastIndexOf('a');System.out.println(index);//0}

listIterator() 迭代器

@Testpublic void test_listIterator(){//返回此列表中的元素的列表迭代器（按适当顺序），从列表中指定位置开始LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};ListIterator<Character> iterator = a.listIterator(1);if(iterator.hasNext()){System.out.println(iterator.next());//d}}

peek() 取第一个

@Testpublic void test_peek(){//获取但不移除此列表的头（第一个元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');add('b');addLast('d');}};Character peek = a.peek();System.out.println(peek);//a}

poll() 取第一个

@Testpublic void test_poll(){//获取并移除此列表的头（第一个元素）LinkedList<Character> a = new LinkedList<Character>() {{add('a');add('b');addLast('d');}};Character poll = a.poll();System.out.println(a);//[b, d]}

pop() 取第一个

@Testpublic void test_pop(){//从此列表所表示的堆栈处弹出一个元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');add('b');addLast('d');}};Character pop = a.pop();System.out.println(pop);//aSystem.out.println(a);//[b, d]}

remove() 移除指定索引元素

@Testpublic void test_remove(){// 移除此列表中指定位置处的元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');add('b');addLast('d');}};a.remove(1);System.out.println(a);//[a, d]}

removeFirst() 移除第一个

@Testpublic void test_removeFirst(){//移除并返回此列表的第一个元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Character character = a.removeFirst();System.out.println(character);//a}

removeLast() 移除最后一个

@Testpublic void test_removeLast(){//移除并返回此列表的最后一个元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Character character = a.removeLast();System.out.println(character);//d}

set() 赋值

@Testpublic void test_set(){//将此列表中指定位置的元素替换为指定的元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Character e = a.set(1, 'e');// Character e1 = a.set(2, 'e');越界了System.out.println(a);//[a, e]}

size() 取大小

@Testpublic void test_size(){//将此列表中指定位置的元素替换为指定的元素LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};System.out.println(a.size());//2}

toArray() 转数组

@Testpublic void test_toArray(){//返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组LinkedList<Character> a = new LinkedList<Character>() {{add('a');addLast('d');}};Object[] objects = a.toArray();System.out.println(objects[1]);//d}