Linkedlist,LinkedList traversal,LinkedList implementation,LinkedList and ArrayList difference,LinkedList thread safety,LinkedList source code

Let’s fuck the interviewer together.

1. Introduction

The collection we are going to study today is LinkedList. Before we study LinkedList, let’s take a look at the interview questions related to LinkedList.

1. Structure of LinkedList. 2. Detailed procedure for inserting elements into LinkedList. 3. Differences between LinkedList and ArrayList. 4….

These interview questions are to test whether we have an understanding of the structure of the linked list, whether we have seen the relevant source code implementation; As long as you read the source code, these questions are very easy to answer; Without further ado, let’s take a look at the source implementation of LinkedList.

Summary of 2.

The LinkedList underlying implementation is a bidirectional LinkedList, which is ideal for queue (first in, first out) and stack (first in, last out) operations; And it implements the List and Deque interface, so it has not only List operations but also queue-related operations; The time complexity of queue and stack dequeueing and stack dequeueing and stack dequeueing is O(1). The schematic diagram of its structure is as follows:

3. The class diagram

AbstractSequentialListAbstract class, which provides the related implementation of the List interface and implementation of the iterative logic, but forLinkedListIt doesn’t mean much becauseLinkedListThe implementation was rewritten extensively
ListInterface, defined the array of add, delete, change, check iteration traversal and other related operations.
CloneableInterface, supportLinkedListcloning
SerializabelInterface, supportLinkedListSerialization and deserialization
DequeInterface that defines operations for inserting and deleting elements at both ends of a queue.

4. The attribute

First let’s look at the definition in the source code:

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable.java.io.Serializable
{
    // List size (number of elements stored)
    transient int size = 0;

    / / head node
    transient Node<E> first;

    / / end nodes
    transient Node<E> last;
    
    // The class that stores the element (node)
    private static class Node<E> {
        // The actual stored element
        E item;
        / / the next node
        Node<E> next;
        / / prev node
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev; }}AbstractList < AbstractList > < AbstractList >
    protected transient int modCount = 0;
}    
Copy the code

NodeIs a node in a linked list that stores data and has three attributesitem(Store elements),next(pointing to the next node),prev(Pointing to the previous node).
sizeNumber of nodes in a bidirectional linked list.
firstBidirectional linked list head, head nodeprevPoint to thenull.
lastBidirectional linked list tail, tail nodenextPoint to thenull.
modCountVersion number, record the number of changes.

5. Common methods

5-1. New

The new LinkedList comes in three categories: the first node, the designated index node, and the last node. First, take a look at the new implementation of the List interface:

// Appends the specified element to the end of the list. This method is equivalent to addLast (E).
public boolean add(E e) {
    linkLast(e);
    return true;
}
// Add the element to the end of the list
void linkLast(E e) {
    // Prestore the endpoints
    final Node<E> l = last; 
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // Determine if it is the first node to be inserted
    if (l == null) 
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}
Copy the code

As can be seen from the figure, last node is pre-stored when adding elements to the end, then a newNode newNode is constructed and connected to the current tail node, then newNode is updated as last node, and finally the node is connected.

Add the following to a specified index node:

// Inserts the specified element at the specified position in this list. Move the current element (if any) and any subsequent elements right (add one to their index) in that position.
public void add(int index, E element) {
    checkPositionIndex(index);
    / / small optimization
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
// Returns the (non-empty) node at the specified element index.
Node<E> node(int index) {
    // assert isElementIndex(index);
    // Small optimization, a binary search
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        returnx; }}// Insert element e before non-null node succ
void linkBefore(E e, Node<E> succ) {
    // assert succ ! = null;
    // Save the last bit of the node
    final Node<E> pred = succ.prev; 
    final Node<E> newNode = new Node<>(pred, e, succ);
    // Link the new node
    succ.prev = newNode; 
    // Determine if succ is the head node
    if (pred == null) 
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
Copy the code

As you can see, there are 5 steps to add an element at the specified index position:

throughnode(int index)Method finds the specified index nodesucc
The specified index node is prestoredsucctheprevNodes forpred
Building a New nodenewNodeAnd joins the specified index nodesucctheprevNode and the specified index nodesucc
The index node is specifiedsucctheprevPoint to thenewNodenode
Will be storedprevnodepredthenextThe node tonewNodenode

The node(int index) method has a minor optimization

// Returns the (non-empty) node at the specified element index.
Node<E> node(int index) {
    // assert isElementIndex(index);
    // Small optimization, a binary search
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        returnx; }}Copy the code

It determines whether the index is in the first half or the second half by a binary method, which reduces the query time by half and improves the query efficiency.

Here is how to add a collection to a linked list in a similar way.

// Appends all elements in the specified collection to the end of this list, returning them in the order in which the specified collection's iterator is returned.
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// Inserts all elements from the specified collection into this list, starting at the specified location.
// Move the current element (if any) and any subsequent elements to the right (increase their index)
// The new elements are displayed in the list in the order returned by the iterators of the specified collection.
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // Check whether the insertion position is valid

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // Store the last element and the element at the current index position
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        // Construct the element
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        // Link to the list
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

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

LinkedList implements not only the List interface, but also the Deque interface.

// Inserts the specified element at the beginning of the list.
public void addFirst(E e) {
    linkFirst(e);
}
// Add the element to the list header
private void linkFirst(E e) {
    // prestore the header
    final Node<E> f = first; 
    // Construct a new node
    final Node<E> newNode = new Node<>(null, e, f); 
    // The new node is upgraded to the head node
    first = newNode;
    // Link the new node to the list
    // Determine if it is the first node to be inserted
    if (f == null) 
        last = newNode;
    else
        f.prev = newNode;
    size++; // Add one to the list size
    modCount++; // Version number + 1
}

// Appends the specified element to the end of the list. This method is equivalent to Add (E).
public void addLast(E e) {
    linkLast(e);
}
// Add the element to the end of the list
void linkLast(E e) {
    // Prestore the endpoints
    final Node<E> l = last; 
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // Determine if it is the first node to be inserted
    if (l == null) 
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// Adds the specified element to the end of the list (the last element).
public boolean offer(E e) {
    return add(e); // add(E e)->linkLast(E e)
}

// Inserts the specified element before this list.
public boolean offerFirst(E e) {
    addFirst(e); // addFirst(E e)->linkFirst(E e)
    return true;
}

// Inserts the specified element at the end of the list.
public boolean offerLast(E e) {
    addLast(e); // addLast(E e)->linkLast(E e)
    return true;
}

// Push elements onto the stack represented by this list. In other words, insert the element before the list. This method is equivalent to addFirst (E).
public void push(E e) {
    addFirst(e); // addFirst(E e)->linkFirst(E e)
}
Copy the code

Through the source code, we find that LinkedList implements the insertion of Deque interface by calling linkFirst(E E) and linkLast(E E), and its insertion process is annotated in detail in the source code.

5 – (2) removed

First let’s look at the LinkedList implementation of the List interface: delete the specified element object and delete the specified node

// If the specified element exists, the first occurrence of that element is removed from the list.
// If the list does not contain the element, it remains unchanged.
Return true if the list contains the specified element.
public boolean remove(Object o) {
    if (o == null) { // Special handling of null values
        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)) { // Define the element object, override equals
                unlink(x);
                return true; }}}return false;
}

// Unlink node X
E unlink(Node<E> x) {
    // assert x ! = null;
    // prestore x Item
    final E element = x.item; 
    // Prestore the next node of the x node
    final Node<E> next = x.next; 
    // Prestore one bit of node on node X
    final Node<E> prev = x.prev; 

    // The last bit of x links to the next bit of x
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    // The next bit of x links to the previous bit of x
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

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

// Remove the element at the specified position in this list. Move all subsequent elements to the left (subtracting one from their index). Returns the element removed from the list.
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
Copy the code

According to the source code, the final deletion is completed through unlink(Node

x), and the process is shown as follows:

Let’s look at the LinkedList implementation of the Deque interface:

// Retrieve and delete the head (the first element) of this list.
public E remove(a) {
    return removeFirst(); // -> unlinkFirst(f)
}

// Remove and return the first element from this list.
public E removeFirst(a) {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

// unlink the first node f that is not empty
private E unlinkFirst(Node<E> f) {
    // assert f == first && f ! = null;
    // Store the first Item
    final E element = f.item; 
    // Save the second node
    final Node<E> next = f.next; 
    f.item = null;
    f.next = null; // help GC
    // Remove the first node
    first = next; 
    // Connect nodes
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

// Remove and return the last element from this list.
public E removeLast(a) {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
// Unlink the last non-empty node L
private E unlinkLast(Node<E> l) {
    // assert l == last && l ! = null;
    // Prestore last Item
    final E element = l.item; 
    // Prestore the penultimate node
    final Node<E> prev = l.prev; 
    l.item = null;
    l.prev = null; // help GC
    // Remove the last node
    last = prev;
    / / the connection
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

// Retrieves and deletes the first element of the list, or returns NULL if the list is empty.
public E pollFirst(a) {
    final Node<E> f = first;
    return (f == null)?null : unlinkFirst(f);
}

// Retrieves and deletes the last element of the list, or returns NULL if the list is empty.
public E pollLast(a) {
    final Node<E> l = last;
    return (l == null)?null : unlinkLast(l);
}

// Retrieve and delete the head (the first element) of this list.
public E poll(a) {
    final Node<E> f = first;
    return (f == null)?null : unlinkFirst(f);
}
Copy the code

From the source we can know that the LinkedList of Deque deletion implementation, ultimately are called unlinkFirst(Node

f) and unlinkLast(Node

L), its removal process is detailed in the source notes.

5 – (3) change

As usual, or first look at the source implementation:

// Replace the element at the specified position in this list with the specified element.
public E set(int index, E element) {
    checkElementIndex(index);
    // Returns the (non-empty) node at the specified element index.
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
Copy the code

The modification process for the LinkedList implementation is simple:

First check if the index is valid>=0&&<size.
Secondly throughnode(int index)Find the node you want to modify.
Last modifieditem, returns the old value.

5-4. Query

LinkedList Query implementations of the List interface include: query by index and query by element (front to back and back to front)

// Returns the element at the specified position in this list.
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Return true if the list contains the specified element.
More formally, if and only if the list contains at least one element (e == null? E == null: O.dice (e)) returns true.
public boolean contains(Object o) {
    returnindexOf(o) ! = -1;
}

// Returns the index of the first occurrence of the specified element in this list; If the list does not contain the element, -1 is returned.
// More formally, return the lowest index I so that (o == null? Get (I) == null: o.dice (get (I)));
If there is no such index, -1 is returned.
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for(Node<E> x = first; x ! =null; x = x.next) {
            if (x.item == null)
                returnindex; index++; }}else {
        for(Node<E> x = first; x ! =null; x = x.next) {
            if (o.equals(x.item))
                returnindex; index++; }}return -1;
}

// Returns the index of the last occurrence of the specified element in this list; If the list does not contain the element, -1 is returned.
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        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

LinkedList query implementation of Deque interface:

Retrieve but do not delete the head of this list (the first element)
public E peek(a) {
    final Node<E> f = first;
    return (f == null)?null : f.item;
}

// Retrieves but does not delete the first element of the list, or returns NULL if the list is empty.
public E peekFirst(a) {
    final Node<E> f = first;
    return (f == null)?null : f.item;
}

// Retrieves but does not delete the last element of the list, or returns NULL if the list is empty.
public E peekLast(a) {
    final Node<E> l = last;
    return (l == null)?null : l.item;
}
Copy the code

6. Summary

From the source we can see that linked list implementation queue and stack is very advantageous, only need to table head and table tail operation can be. And the LinkedList property just holds the header and tail references, so the entire operation is O(1) time.

Now let’s look at the first interview questions:

1. Structure of LinkedList. 2. Detailed procedure for inserting elements into LinkedList. 3. Differences between LinkedList and ArrayList.

Two questions can be easily answered by learning the source code. We focus on the third question: the difference between LinkedList and ArrayList.

Through the last article “Let’s learn collections” -ArrayList article learning, we can know that the underlying ArrayList is based on array implementation to support dynamic expansion of a data structure

The differences between random accesses and random insertions and deletions (due to moving elements) and linkedLists are as follows:

Different structures:ArrayListIs based on arrays,LinkedListIs based on nodesNode
Different efficiency:ArrayListRandom access ratioLinkedListHigh efficiency becauseLinkedListThe search must be iterated over each time
Different storage:ArrayListA large amount of continuous storage space is required, and more storage debris will be generated after continuous expansionLinkedListIt doesn’t require contiguous storage, which means it can use more memory, but it also consumes more memory for each element, because it has to keep each node’sprevandnextReferences.

In theory, ArrayList is less efficient than LinkedList in deleting an element, because ArrayList deleting an element that is not the end produces a copy of the element, whereas LinkedList deleting an element only changes references to the nodes before and after it.

In theory, yes, but in practice, thanks to modern computer architectures (CPU caching), ArrayList would be much more efficient in almost every possible use case. Nodes, mainly LinkedList, are randomly distributed throughout memory. RAM (” random-access memory “) is not truly random and blocks of memory need to be fetched for caching. This operation takes time, and the memory pages in the cache need to be replaced all the time when such fetches occur frequently -> cache misses -> cache efficiency is not high. ArrayList elements are stored in contiguous memory, which is better for caching. This is what modern CPU architectures are optimizing for.

Personally, I think the selection of ArrayList and LinkedList is a complex issue, which needs to be decided according to different scenarios and considerations. I prefer to use ArrayList in general.

Reference article:

Stackoverflow.com/questions/3…

Stackoverflow.com/questions/1…

Let’s fuck the interviewer together.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Let’s get Together -LinkedList

1. Introduction

Summary of 2.

3. The class diagram

4. The attribute

5. Common methods

5-1. New

5 – (2) removed

5 – (3) change

5-4. Query

6. Summary

Let’s get Together -LinkedList

1. Introduction

Summary of 2.

3. The class diagram

4. The attribute

5. Common methods

5-1. New

5 – (2) removed

5 – (3) change

5-4. Query

6. Summary

Related Posts

How to brush leetcode

Java memory regions and garbage collection algorithms

In those years, the basic data structure and algorithm of common interview questions (below) | the nuggets technical essay