@[TOC]

Introduction to the

1. LinkedList is implemented based on a LinkedList, which is a bidirectional LinkedList as you can see from the UML diagram. In addition to being used as a linked list, it can also operate as a stack, queue, or double-endian queue. Not thread-safe, AbstractSequentialList implementation List, Deque, Cloneable, Serializable.
2. LinkedList is implemented based on linked lists, so insertions and deletions are efficient and lookups are inefficient (although there is an accelerated action)
3. LinkedList is implemented based on linked lists, so there is no capacity problem, so there is no way to expand
4. If you want to use LinkedList to become thread-safe, you call the synchronizedList method in the static class Collections class

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable.java.io.Serializable
Copy the code

• Inheriting AbstractSequentialList, AbstractSequentialList implements get(int index), set(int index, E element), Add (int index, E element), and remove(int index) functions.

• Implement the List interface, it can carry out queue operations

• Implement the Deque interface and use the LinkdList as a double-ended queue

• Cloneable interface is implemented, that is, clone

• Implement the Java.io.Serializable interface, which means that LinkedList supports serialization and can be transmitted via serialization.

The internal structure

    /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item ! = null) */
    transient Node<E> first;

    /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item ! = null) */
    transient Node<E> last;
Copy the code

private static class Node<E> {
        E item; / / the node values
        Node<E> next; // Next node
        Node<E> prev; // Last node

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev; }}Copy the code

This class represents the Node of a double-ended list. This class has three attributes: the value of the node, the next node, and the previous node

Source code analysis

1. Construction method

Empty constructor:

    public LinkedList(a) {}Copy the code

Collection create linked list constructor:

public LinkedList(Collection<? extends E> c) {
        this(a); addAll(c); }Copy the code

2. The add method

The add(E E) method adds an element to the end of the list

    public boolean add(E e) {
        linkLast(e); // Add to the last element of the list
        return true;
    }
Copy the code

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode; // Create a node
        if (l == null)
            first = newNode;
        else
            l.next = newNode; // points to the next element
        size++;
        modCount++;
    }
Copy the code

Add (int index, E Element) : Adds an element at the specified position

public void add(int index, E element) {
        checkPositionIndex(index); // Check whether the index is between [0-size]

        if (index == size) 
            linkLast(element); // Add to the end of the list
        else
            linkBefore(element, node(index)); // Add to the middle of the list
    }
Copy the code

• The linkBefore method takes two arguments, the value of the insertion node and the specified node

   void linkBefore(E e, Node<E> succ) {
        // assert succ ! = null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
Copy the code

addAll(Collection<? Extends E> c) method: Adds an element to the end of the list

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
Copy the code

public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index); // Check if the index is in range

        Object[] a = c.toArray(); The toArray() method stores the collection's data into an array
        int numNew = a.length;
        if (numNew == 0)
            return false;
		// Get the front and back nodes
        Node<E> pred, succ;
        if (index == size) {  // If index == 0, the first Node initializes a Node and the second Node is null
            succ = null;
            pred = last; 
        } else {   // Instead of 0, call node() to get the back node and the front node
            succ = node(index);
            pred = succ.prev;
        }
		// Iterate over the data to insert the data
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            // Superkey new node
            Node<E> newNode = new Node<>(pred, e, null);
            // If the insertion position is in the header of the table
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
		// If the insertion position is at the end, reset the last node
        if (succ == null) {
            last = pred;
        } else { // Otherwise, join the inserted list with the previous list
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }
Copy the code

AddAll methods are divided into:

1. Check whether the following table for index is between 0 and size
2. ToArray stores the collection’s data into an array of objects
3. Get the front and back nodes of the insertion position
4. Compare the data there and insert the data into the specified location

AddFirst (E E) : Adds an element to the head of the list

 public void addFirst(E e) {
        linkFirst(e);
    }
Copy the code

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);  // Create a node
        first = newNode;
        // If the list is empty, the last node also points to that node
        if (f == null)
            last = newNode;
            // Otherwise, point to the previous element
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
Copy the code

AddLast (E E) : Adds elements to the end of the list, just like the add(E E) method

public void addLast(E e) {
        linkLast(e);
    }
Copy the code

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
Copy the code

3. Obtain data based on location

Get (int index) : returns data according to the specified index

public E get(int index) {
		// check index range
        checkElementIndex(index);
        // Call Node (index) to find the Node corresponding to index and return its value
        return node(index).item;
    }
Copy the code

GetFirst () : Gets the header element

 public E getFirst(a) {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
Copy the code

GetLast () : Gets the tail element

public E getLast(a) {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
Copy the code

4. Obtain the index by object

IndexOf (Object O) : Traverses the search from the beginning

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
        	//x = first iterates the query from the beginning
            for(Node<E> x = first; x ! =null; x = x.next) {
                if (x.item == null)
                    returnindex; index++; }}else {
        	//x = first iterates the query from the beginning
            for(Node<E> x = first; x ! =null; x = x.next) {
                if (o.equals(x.item))
                    returnindex; index++; }}return -1;
    }
Copy the code

Int lastIndexOf(Object O) : Search from the end

public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
        	// x is last traversed from the tail
            for(Node<E> x = last; x ! =null; x = x.prev) {
                index--;
                if (x.item == null)
                    returnindex; }}else {
            for(Node<E> x = last; x ! =null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    returnindex; }}return -1;
    }
Copy the code

5. Whether to contain elements

Contains (Object O) : Indicates whether the Object exists in the linked list

public boolean contains(Object o) {
		// Call indexOf to traverse the query
        returnindexOf(o) ! = -1;
    }
Copy the code

6. Delete

Remove () : removes the head node

public E remove(a) {
		// Call the method to remove the head node
        return removeFirst();
    }
Copy the code

public E removeFirst(a) {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
Copy the code

private E unlinkFirst(Node<E> f) {
        // assert f == first && f ! = null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
Copy the code

Poll () : Deletes the header element

public E poll(a) {
        final Node<E> f = first;
        return (f == null)?null : unlinkFirst(f);
    }

Copy the code

RemoveLast () : Removes the tail element

public E removeLast(a) {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
Copy the code

PollLast () : Remove the tail element

public E pollLast(a) {
        final Node<E> l = last;
        return (l == null)?null : unlinkLast(l);
    }
Copy the code

Remove (Object O) : Deletes objects based on elements

    public boolean remove(Object o) {
    	// If the object is null, we can insert null values
        if (o == null) {
        	// x == first iterates through the elements from the beginning
            for(Node<E> x = first; x ! =null; x = x.next) {
            	// Find the element
                if (x.item == null) {
                	// Remove the element
                    unlink(x);
                    return true; }}}else {
        	// x == first iterates through the elements from the beginning
            for(Node<E> x = first; x ! =null; x = x.next) {
                if (o.equals(x.item)) {
                	// Delete the element from the list
                    unlink(x);
                    return true; }}}return false;
    }

Copy the code

Unlink (Node x)

    E unlink(Node<E> x) {
        // assert x ! = null;
        final E element = x.item;
        final Node<E> next = x.next; // Get the next node
        final Node<E> prev = x.prev; // Get the last node
		// If = null
        if (prev == null) {
            first = next; // Point the first node to the next element
        } else {
            prev.next = next; // The next node of the previous node specifies the next node
            x.prev = null;
        }
		// Delete the next element
        if (next == null) {
            last = prev; // If the last node is deleted, make it point to the previous node of the node
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }
Copy the code

Remove (int index) : deletes the element at the specified position

public E remove(int index) {
        // Check the index range
        checkElementIndex(index);
        // Delete the node
        return unlink(node(index));
    }
Copy the code

---

Personal blog address: blog.yanxiaolu.cn /