A: LinkedList source code analysis

1.1 Member Variables

// Length transient int size = 0; // Transient Node<E> first; // Transient Node<E> last;Copy the code

Static inner class

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; }}Copy the code

1.2 Construction method

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

1.3 the add operation

Add an element to the end of the list:

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    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

First, set the precursor node of E to the last node in the current linked list, and set the post-node to null. Then determine whether the last node is null. If it is null, e is regarded as the first node. Otherwise, the next of the last node points to E.

Add an element at the specified location:

public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } Node<E> node(int index) { // assert isElementIndex(index); 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; return x; } } 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

First find the node at index, set the precursor node of E as the precursor node of index, and set the back-end node of E as the node at index.

1.4 get operation

public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); 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; return x; }}Copy the code

If index is less than half the length of the list, it traverses backwards from the beginning node, otherwise it traverses forwards from the last node.

1.5 remove operation

Delete the element at the specified position:

public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(Node<E> x) { // assert x ! = null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } x.item = null; size--; modCount++; return element; }Copy the code

The prev node of the index node is set to the next node of the index node, and the precursor pointer of the index node is disconnected. Next, set the precursor node of the next node to the precursor node of the index node, disconnect the post-pointer of the index node, and set the value of the index node to NULL.

Delete element:

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; }Copy the code

Iterate through the linked list from the beginning, comparing whether the values of the nodes are equal, and deleting them if they are.

1.6 POP, poll, Push, peek, offer

1.7 traversal

public static void main(String[] args) { LinkedList<Integer> list = getLinkedList(); // Iterate over LinkedList listByNormalFor(list) with a quick random access; // Iterate over LinkedList listByStrongThenFor(list) by enhancing the for loop; // Iterate over LinkedList listByIterator(list); } @return */ private static LinkedList<Integer> getLinkedList() {LinkedList list = new LinkedList(); for (int i = 0; i < 50000; i++){ list.add(i); } return list; }Copy the code

• Normal for loop

Private static void listByNormalFor(LinkedList<Integer> list) {// Record the start time long start = System.currentTimeMillis(); int size = list.size(); for (int i = 0; i < size; i++) { list.get(i); } // Long interval = system.currentTimemillis () -start; System.out.println("listByNormalFor: "+ interval +" ms"); }Copy the code

• Enhanced for loop

Public static void listByStrongThenFor(LinkedList<Integer> list){// Record the start time  long start = System.currentTimeMillis(); For (Integer I: list) {} long interval = system.currentTimemillis () -start; System.out.println("listByStrongThenFor: "+ interval +" ms"); }Copy the code

• The Iterator Iterator

Private static void listByIterator(LinkedList<Integer> list) {private static void listByIterator(LinkedList<Integer> list System.currentTimeMillis(); for(Iterator iter = list.iterator(); iter.hasNext();) { iter.next(); } // Long interval = system.currentTimemillis () -start; System.out.println("listByIterator: "+ interval +" ms"); }Copy the code

Time comparison:

ListByNormalFor: 1042 ms listByStrongThenFor: 8 ms listByIterator: 4 msCopy the code

A normal for loop takes much longer than iterator traversal.

2. Linkedin List Interview Questions

2.1 The difference between LinkedList and ArrayList?

• An ArrayList is an array, memory contiguous; LinkedList is a node and memory is not contiguous.
• Because memory is continuous, the time complexity of ArrayList lookup is O(1) and that of insert and delete is O(n). LinkedList lookup is O(n) and insert and delete is O(1).

2.2 How to implement stack and queue data structures with LinkedList?

public class MyStack { private LinkedList list; public MyStack() { this.list = new LinkedList(); } public void push(Object o) { this.list.addLast(o); } public Object pop() {// stack return this.list.removelast (); // queue //return this.list.removeFirst(); } public boolean isEmpty() { return this.list.isEmpty(); }}Copy the code

2.3 Why is a normal for loop slower than an iterator?

Because a normal for loop iterates from the beginning node each time, the iterator points the cursor to the next node for each element, and the cursor leads directly to the next element.

Third, summary

• LinkedList is a bidirectional LinkedList with discontinuous memory address. The time complexity of search is O(n), and the time complexity of insert and delete is O(1).
• Try not to iterate through the LinkedList with a normal for loop.