# preface

The linked list structure should be clear to everyone. LinkedList is implemented based on two-way linked list. The previous article briefly analyzed ArrayList, which is implemented based on array; This article will make a simple analysis of LinkedList. As long as you understand the structure of the linked list, the source code looks very simple, just the binding and unbinding operation between nodes.

# 1, Data and linked list

The two-way linked list has three important attributes: node (data node), PRED (previous node) and next (next node). It is linked together through the association relationship between nodes. The advantage of this is that it increases, deletes and traverses faster, but its random search is slower than the array. The search for an element in a normal array is calculated through binary search, Faster query efficiency; The linked list can only traverse from the beginning to the end to find the corresponding elements.

# 2, LinkedList

LinkedList is implemented based on a two-way linked list. A Node class is defined inside it to represent the nodes of the linked list.

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

## Core attribute

There is a Node class inside the LinkedList, which is a Node in the linked list. Needless to say, it is basically clear to those who understand the basic data structure.

Core properties of LinkedList:

- size: also records the length of internal elements of LinkedList.
- First: the first element.
- Last: the last element.

## Core method

### Construction method

The construction method of LinkedList does not specify the size, because its implementation is a linked list without specifying the size.

Let's not talk about parameterless construction. There's nothing. Let's take a look at the construction method of passing Collection.

public LinkedList(Collection<? extends E> c) { this(); addAll(c); } /** * The core method is addAll, which converts the contents of other types of collections into linked list form */ public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); //Convert collection to array Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; //Find the corresponding node Node<E> pred, succ; if (index == size) { //At first, the size and index are the same, both 0 succ = null; pred = last; } else { //Don't go here at the beginning. You can only go here when there is data in the linked list succ = node(index); //Find the corresponding index of the node pred = succ.prev; } //Loop through for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) //For the first time, pred is empty, and the head node is the created node first = newNode; else //Sets the link point between nodes pred.next = newNode; pred = newNode; //Assign the intermediate value again } //Assign the last node as the last node after traversal if (succ == null) { last = pred; } else { //Establish the link between the two linked lists pred.next = succ; succ.prev = pred; } size += numNew; //size is set to the common length of the two linked lists modCount++; return true; } /** * Node lookup */ Node<E> node(int index) { //If the passed in index is less than the length of the current linked list / 2, search from left to right if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; //If the passed in index is greater than the length of the current linked list / 2, search from right to left } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

## add() method

public boolean add(E e) { linkLast(e); return true; } //Hang the added node at the end of the linked list 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++; }

## get() method

Directly return the element bound by the subscript node

public E get(int index) { checkElementIndex(index); return node(index).item; }

## remove() method

The remove() method of LinkedList also has subscript removal and object removal

Subscript removal:

public E remove(int index) { checkElementIndex(index); //Find the element at the subscript position and unlink it return unlink(node(index)); }

Object removal, first traverse to find the corresponding element, and then unlink:

public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }

Take a look at the method of unlinking:

E unlink(Node<E> x) { //Gets the element in x, the previous node and the next node final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //If the previous node is empty, then x is the head node, and set the next node as the head node; If the previous node is not empty, bind the previous node and the next node together if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } //If the next node is empty, then x is the tail node. Set the previous node as the tail node; If the next node is not empty, bind the previous node and the next node together if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } //If the reference of the X element position is set to null, and the links between the upper and lower nodes of X are also disconnected and set to null, then x is completely released and will be recycled during garbage collection x.item = null; size--; modCount++; return element; }

The size() method is also omitted. Although the linked list has no length, there is a size inside the LinkedList, which always records how many elements are currently stored.