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 30

        dll.remove(20);
        dll.printList();  // 打印: 10 30
    }
}

下面是一些它的方法：

add() 末尾添加元素

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

addIndex() 指定索引添加元素

@Test
    public void test_addIndex(){
        //在此列表中指定的位置插入指定的元素
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            add(0,'b');
        }};

        System.out.println(a);//[b, a]
    }

addAll() 往里加一个集合

@Test
    public 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() 头位置添加

@Test
    public void test_addFirst(){
        //将指定元素插入此列表的开头
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addFirst('c');
        }};

        System.out.println(a);//[c, a]
    }

addLast() 末尾添加

@Test
    public void test_addLast(){
        //将指定元素添加到此列表的结尾
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        System.out.println(a);//[a, d]
    }

clear()

@Test
    public void test_clear(){
        //从此列表中移除所有元素
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        a.clear();
        System.out.println(a);//[]
    }

clone()

@Test
    public 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() 是否包含

@Test
    public void test_contains(){
        //如果此列表包含指定元素，则返回 true
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        boolean a1 = a.contains('a');
        System.out.println(a1);//true
    }

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

@Test
    public void test_element(){
        //获取但不移除此列表的头（第一个元素）。
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        Character element = a.element();
        System.out.println(element);//a
        System.out.println(a);//[a, d]
    }

get() 按索引取值

@Test
    public void test_get(){
        //获取但不移除此列表的头（第一个元素）。
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        Character character = a.get(1);
        System.out.println(character);//d
    }

getFirst()

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

        Character first = a.getFirst();
        System.out.println(first);//a
    }

getLast()

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

        Character last = a.getLast();
        System.out.println(last);//d
    }

indexOf() 按值取索引

@Test
    public 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() 最后位置出现的索引

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

        int index = a.lastIndexOf('a');
        System.out.println(index);//0
    }

listIterator() 迭代器

@Test
    public 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() 取第一个

@Test
    public 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() 取第一个

@Test
    public 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() 取第一个

@Test
    public void test_pop(){
        //从此列表所表示的堆栈处弹出一个元素
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            add('b');
            addLast('d');
        }};

        Character pop = a.pop();
        System.out.println(pop);//a
        System.out.println(a);//[b, d]
    }

remove() 移除指定索引元素

@Test
    public 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() 移除第一个

@Test
    public void test_removeFirst(){
        //移除并返回此列表的第一个元素
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        Character character = a.removeFirst();
        System.out.println(character);//a
    }

removeLast() 移除最后一个

@Test
    public void test_removeLast(){
        //移除并返回此列表的最后一个元素
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        Character character = a.removeLast();
        System.out.println(character);//d
    }

set() 赋值

@Test
    public 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() 取大小

@Test
    public void test_size(){
        //将此列表中指定位置的元素替换为指定的元素
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        System.out.println(a.size());//2
    }

toArray() 转数组

@Test
    public void test_toArray(){
        //返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组
        LinkedList<Character> a = new LinkedList<Character>() {{
            add('a');
            addLast('d');
        }};

        Object[] objects = a.toArray();
        System.out.println(objects[1]);//d

    }