One, foreword

In the previous two chapters, we explained dynamic arrays, stacks and queues, which all rely on static arrays and resize to solve the problem of fixed capacity. Although the user saw dynamic arrays before, he still used static arrays. He solved the problem of fixed capacity by resize. But what we’re going to talk about today is a different kind of linked list. Linked lists are an important part of our data structure study, and they can also be a difficult part. Why are linked lists so important? Because it is the simplest and truly dynamic data structure.

Why are linked lists important

  • A linked list is a truly dynamic data structure
  • Simplest dynamic data structure
  • Better understand references (or Pointers)
  • Better understand recursion
  • Assist in composing other data structures

A more thorough understanding of reference (or pointer) : related to memory, although we don’t have to manually manage memory in Java, but the linked list This kind of data structure, more in-depth understanding, can help you for references, Pointers, and even computer system and memory management related many topics, have more in-depth understanding.

Better understanding of recursion: Linked lists have very clear recursion structures, and because linked lists are data structures, we can understand recursion in a way that is not accessible.

Linked lists are also functional in their own right: they assist in composing other data structures (hashMaps, stacks, and queues)

What is a linked list

A linked list is a kind of data structure, which is stored in memory by connecting nodes to form a chain. Compared with an array, linked lists do not need contiguous areas in memory, and only need each node to record the memory address of a node for reference search. This feature makes the operation of adding and deleting a linked list consume very little time, but the search time is very large.

The LinkedList we use everyday in Java is a two-way LinkedList. The linked list is realized by its basic component unit Node (Node). Most of the linked lists we see in our daily life are single and double linked lists

Unit Node:

class Node{
	E e;
	Node next;
}
Copy the code
  • E is the list element
  • Next refers to the next node of the current node
  • For linked list, it is just like our train, each node is actually a car, we store real data in the car, and the connection between the car and the car, so that our data is integrated, users can easily query or other operations on all the data. So the data and the data connection is done by this next
  • Of course, a linked list cannot be endless. If next is Null for a node, that node is the last one

As shown below (single linked list) :



Advantages of linked lists: true dynamic, no need to deal with fixed capacity issues

Disadvantages of linked lists: Lost random access

In an array: each index, directly from out indexes corresponding element in the array, this is because, from the underlying mechanism of the array of open space, in the memory is a continuous distribution, so we can directly find the array offset, directly calculate the data stored by the memory address, can be used directly.

Linked list: The linked list is connected layer by layer by Next, and we need to use this Next to find the elements we need to take out bit by bit.

Create our own linked list

4.1 Basic structure of linked lists

/** * The inner class of the underlying list *@param <E>
 */
public class LinkedList<E> {

    // Design private inner classes, for the user does not need to know the list underlying implementation,
    // Do not need to know the node, the user to mask the implementation of the underlying implementation
    private class Node{
        public E e;
        public Node next;// Public can be manipulated on LinkedList

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(a){
            this(null.null);
        }

        @Override
        public String toString(a) {
            returne.toString(); }}}Copy the code

Inner class Node: Design a private inner class that does not require the user to know the underlying implementation of the linked list. It does not require the user to know the Node. The underlying implementation of the encoding implementation e: element next: a reference to Node

4.2 Adding Elements

Before we’re only talking about how to add elements in the array, we added in the array element is very convenient, because the emissions in order for an array is, interestingly for chain table, on the contrary, adding in the head element is very convenient, actually this is very good understanding, we have the size for an array of this variable, It points directly to the last element in the array and next to the next element to be added, so it’s very easy to add, because we have size, which is tracking the tail of the array, and for lists we have a head, There are no variables to track the tail of the list, so it is very convenient to add elements to the head of the list, the most important being Node. next = head and head = node, as shown below:

4.2.1 Adding elements to the list header

Code implementation:

    // Add element e to the list header
    public void addFirst(E e){
		/ / way
		// Node node = new Node(e);
		// node.next = head;
		// head = node;
		2 / / way
        head = new Node(e,head);
        size ++;
    }
Copy the code
4.2.2 Adding elements in the middle of a linked List:

We need to add elements at index 2666We just need to findElements 666toInsert previous node (1)We call itprevAnd then the(1) next of the previous nodePoint to the666, and then in the666theNode points to previous node (1) 的 Next node (2)That completes the insert, and the key code isNode. next = prev.next and prev.next = node;.The key: we need to find the previous node to which we added the node 。



Code implementation:

  // Add a new element e at index(0-based)
    public void add(int index,E e){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        if(index == 0)
            addFirst(e);
        else{
            Node prev = head;
            for (int i = 0; i < index - 1; i++) {// Put the prev into the next node until it moves to index-1
                prev = prev.next;

                / / way
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;

                2 / / way
                prev.next = newNode(e,prev.next); size++; }}}// Add a new element e to the end of the list
    public void addLast(E e){
        add(size,e);
    }
Copy the code
4.2.3 Adding the operation time complexity
function Time complexity
addList(e) O(n)
addFirst(e) O(1)
add(index,e) O(n/2) = O(n)

4.3 Design virtual headers for linked lists

We introduced the above list to add operation, so we met a problem when I add, is a place in the list, add an element, the chain add a header element, as well as the rest of the list add elements, there will be differences on logic, why add elements in the chain header will be special, because we are in the process of adding element on the list, To find before to add a node, but as for the head without a node before, but we can create a head node, the node is the virtual head node, the node for the user does not exist, the user will not perceive the existence of this node, we are blocked by the existence of this node, as shown in the figure below:



Code implementation:

 private Node dummyHead;
    int size;

    public LinkedList(a){
        dummyHead = new Node(null.null);
        size = 0;
    }


    // Get the number of elements in the list
    public int getSize(a){
        return size;
    }

    // Returns whether the list is empty
    public boolean isEmpty(a){
        return size == 0;
    }
    // Add a new element e at index(0-based)
    public void add(int index,E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        prev.next = new Node(e,prev.next);
        size ++;
    }

  // Add element e to the list header
    public void addFirst(E e){
        add(0,e);
    }

    // Add a new element e to the end of the list
    public void addLast(E e){
        add(size,e);
    }
Copy the code

4.4 Linked list elements get, set, whether there are operations

 // Add a new element e at index(0-based)
    public E get(int index){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Get failed. Illegal index.");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;

        return cur.e;
    }

    // Get the first element of the list
    public E getFirst(a){
        return get(0);
    }

    // Get the last element of the list
    public E getLast(a){
        return get(size - 1);
    }

    // Add a new element e at index(0-based)
    public void set(int index,E e){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;

        cur.e = e;
    }

    // Find if there is an element e in the list
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur ! =null) {if(cur.e.equals(e))
                return  true;
            cur = cur.next;
        }
        return false;
    }
Copy the code
4.5.1 Changing the time complexity of search operations
function Time complexity
set(index,e) O(n)
get(index) O(n)
contains(e) O(n)

4.5 Deleting linked list elements

To add the element whose index is (2) we want to delete, we need to find a position before the node to be deleted, namely (1), which is denoted by prev. After finding this node, then (2) is the index we need to delete, which is called delNode, as shown in the following figure:



Code implementation:


    // Remove the Index(0-based) position from the list, return the deleted element
    public E remove(int index){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Remove failed. Illegal index.");

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;

        size --;

        return  retNode.e;

    }

    // Remove the element at the first position from the list
    public E removeFirst(a){
        return remove(0);
    }

    // Remove the element from the last position in the list
    public E removeLast(a){
        return remove(size - 1);
    }
Copy the code
4.5.1 Complexity of Deletion Operation Time
function Time complexity
removeList(e) O(n)
removeFirst(e) O(1)
remove(index,e) O(n/2) = O(n)

4.6 Complete Code


/** * The inner class of the underlying list *@param <E>
 */
public class LinkedList<E> {

    private class Node{
        public E e;
        public Node next;// Public can be manipulated on LinkedList

        public Node(E e,Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(a){
            this(null.null);
        }

        @Override
        public String toString(a) {
            returne.toString(); }}private Node dummyHead;
    int size;

    public LinkedList(a){
        dummyHead = new Node(null.null);
        size = 0;
    }


    // Get the number of elements in the list
    public int getSize(a){
        return size;
    }

    // Returns whether the list is empty
    public boolean isEmpty(a){
        return size == 0;
    }




    // Add element e to the list header
    public void addFirst(E e){
/ / way
// Node node = new Node(e);
// node.next = head;
// head = node;
2 / / way
        add(0,e);
    }

    // Add a new element e at index(0-based)
    public void add(int index,E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        prev.next = new Node(e,prev.next);
        size ++;
    }

    // Add a new element e to the end of the list
    public void addLast(E e){
        add(size,e);
    }

    // Add a new element e at index(0-based)
    public E get(int index){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Get failed. Illegal index.");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;

        return cur.e;
    }

    // Get the first element of the list
    public E getFirst(a){
        return get(0);
    }

    // Get the last element of the list
    public E getLast(a){
        return get(size - 1);
    }

    // Add a new element e at index(0-based)
    public void set(int index,E e){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++)
            cur = cur.next;

        cur.e = e;
    }

    // Find if there is an element e in the list
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur ! =null) {if(cur.e.equals(e))
                return  true;
            cur = cur.next;
        }
        return false;
    }


    // Remove the Index(0-based) position from the list, return the deleted element
    public E remove(int index){
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Remove failed. Illegal index.");

        Node prev = dummyHead;
        for (int i = 0; i < index; i++)
            prev = prev.next;

        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;

        size --;

        return  retNode.e;

    }

    // Remove the element at the first position from the list
    public E removeFirst(a){
        return remove(0);
    }

    // Remove the element from the last position in the list
    public E removeLast(a){
        return remove(size - 1);
    }

    @Override
    public String toString(a) {

        StringBuilder res = new StringBuilder();
        for(Node cur = dummyHead.next; cur ! =null; cur= cur.next)
            res.append(cur + "- >");

        res.append("Null");
        returnres.toString(); }}Copy the code

4.2.7 Result Test:

public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        // Add elements 0-4
        for (int i = 0; i < 5 ; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }

        // Add the second element add 666
        linkedList.add(2.Awesome!);
        System.out.println(linkedList);

        // Remove the second element 666
        linkedList.remove(2);
        System.out.println(linkedList);

        // Delete the first element
        linkedList.removeFirst();
        System.out.println(linkedList);

        // Remove the last element
        linkedList.removeLast();
        System.out.println(linkedList);
    }
    
Copy the code

Print result:

0->Null
1->0->Null
2->1->0->Null
3->2->1->0->Null
4->3->2->1->0->Null
4->3->666->2->1->0->Null
4->3->2->1->0->Null
3->2->1->0->Null
3->2->1->Null
Copy the code

4. Time complexity analysis of linked lists

function Time complexity
increase O(n)
delete O(n)
Modify the O(n)
The query O(n)

For additions and deletions, this is O(1) complexity if you operate on linked headers, and the same is true for queries

5. Linked list application

5.1 Using stacks to implement linked lists

5.1.1 Interface Classes:
/ * * *@program: Data-Structures
 * @ClassName Stack
 * @description:
 * @author: lyy
 * @create: the 2019-11-20 21:51 *@Version1.0 * * /
public interface Stack<E> {

    int getSize(a);
    boolean isEmpty(a);
    void push(E e);
    E pop(a);
    E peek(a);

}
Copy the code
5.1.2 Implementation Classes:

import com.lyy.datasty.Mystack.Stack;

// List stack implementation
public class LinkedListStack<E> implements Stack<E> {

    private LinkedList1<E> list;

    public LinkedListStack(a){
        list = new LinkedList1<>();
    }


    @Override
    public int getSize(a) {
        return list.getSize();
    }

    @Override
    public boolean isEmpty(a) {
        return list.isEmpty();
    }

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop(a) {
        return list.removeFirst();
    }

    @Override
    public E peek(a) {
        return list.getFirst();
    }

    @Override
    public String toString(a) {

        StringBuilder res = new StringBuilder();
        res.append("Stack: top");
        res.append(list);
        returnres.toString(); }}Copy the code
5.1.3 Operating Results:
  public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>();
        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);


    }
Copy the code
5.1.4 Result Printing:
Stack: top 0->Null Stack: top 1->0->Null Stack: top 2->1->0->Null Stack: top 3->2->1->0->Null Stack: Top 4 - > 3 - > 2 - > 1 - > 0 - > Null Stack: the top 3 - > 2 - > 1 - > 0 - > NullCopy the code

5.2 Implementing queues using linked lists

5.2.1 interface class
/ * * *@program: Data-Structures
 * @ClassName Queue
 * @description:
 * @author: lyy
 * @create: 21:54 * 2019-11-21@Version1.0 * * /
public interface Queue<E> {

    int getSize(a);
    boolean isEmpty(a);
    void enqueue(E e);
    E dequeue(a);
    E getFront(a);


}
Copy the code
5.2.2 implementation class
public class LinkedListQueue<E> implements Queue<E>{

    // Design private inner classes, for the user does not need to know the list underlying implementation,
    // Do not need to know the node, the user to mask the implementation of the underlying implementation
    private class Node{
        public E e;
        public Node next;// Public can be manipulated on LinkedList

        public Node(E e, Node next){
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node(a){
            this(null.null);
        }

        @Override
        public String toString(a) {
            returne.toString(); }}private Node head,tail;
    private int size;

    public LinkedListQueue(a){
        head = null;
        tail = null;
        size = 0;
    }


    @Override
    public int getSize(a) {
        return size;
    }

    @Override
    public boolean isEmpty(a) {
        return size == 0;
    }

    @Override
    public void enqueue(E e) {
        if(tail == null){
            tail = new Node(e);
            head = tail;
        }else{
            tail.next = new Node(e);
            tail = tail.next;
        }
        size ++;
    }

    @Override
    public E dequeue(a) {
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if(head == null)
            tail = null;

        size --;

        return retNode.e;
    }

    @Override
    public E getFront(a) {
        if(isEmpty())
            throw new IllegalArgumentException("queue is empty.");

        return head.e;
    }

    @Override
    public String toString(a) {
        StringBuilder res = new StringBuilder();
        res.append("The Queue: front");

        Node cur = head;
        while(cur ! =null) {
            res.append(cur + "- >");
            cur = cur.next;
        }
        res.append("Null tail");
        returnres.toString(); }}Copy the code
5.2.2 test class
  public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3= =2){ queue.dequeue(); System.out.println(queue); }}}Copy the code

Print result:

Queue: front 0 - > Null tail Queue: front 0-1 - > > Null tail Queue: front 0 - > 1 - > 2 - > Null tail Queue: front 1 - > 2 - > Null tail Queue: Front 1->2->3->Null tail Queue: front 1->2->3->4->Null tail Queue: front 1->2->3->4->5->Null tail Queue: front 1->2->3->4->5->Null tail Queue: front 1->2->3->4->5->Null tail Queue: Front 2->3->4->5->Null tail Queue: front 2->3->4->5->6->Null tail Queue: front 2->3->4->5->6->7->Null tail Queue: front 2->3->4->5->6->7->Null tail Queue: The front 4 - > 2 - > 3 - > 5 - > 6-7-8 - > > > Null tail Queue: front 3 - > 4 - > 5 - > 6-7-8 - > > > Null tail Queue: front 3 - > 4 - > 5 - > 6-7-8-9 - > > > > Null tailCopy the code

6. More linked list structures

6.1 double linked list



Code:

class Node{
	E e;
	Node next,prev;
}
Copy the code

6.1 Circular List



Code:

class Node{
	E e;
	Node next,prev;
}
Copy the code

In Java, LinkedList substrate is circular linked list, which is circulating two-way linked list, here we list is completed, if you find these have improvements or questions in reading, you are welcome to leave a message below, blogger, saw the will reply you the first time, I was small, I feed themselves with salt, Study on the road you and I go together, everyone come on!