Hands-on coding - Linked lists (Java implementation)

preface

EnsureCapacity is a method that rewrites an array 1.5 times the size of the original array when the array is running out of capacity. Copying the elements from the original array into the new array, with Pointers to the new array, is fundamentally not really dynamic.

At the same time, the array copy, and the array space does not store all elements, will reduce efficiency, and will cause a waste of memory space, but for linked lists, this is not a problem, linked lists can be used to allocate as much memory space as possible, which is the real dynamic data structure.

concept

What is a linked list?

A linked list is a linear list of chained storage where the memory addresses of all elements are not necessarily contiguous

The structure of linked lists

For linked lists, data is stored in “nodes”. You can use a data field to store data, which I’ll call element. And then there’s a node field that points to the next node, usually called next. The end of a linked list is usually NULL, so the node field of the last node in the list next points to NULL. The structure of the linked list is shown in the following figure:

Design of linked lists

/** * defines the first node of the list, pointing to the first element */
private Node<E> first;

/** * defines the Node class, which contains elements and an address reference to the next Node@param <E>
  */
private static class Node<E>{
    E element;
    Node<E> next;

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

The Node class is the definition of nodes in the linked list. The first Node is used to store the number of elements in the linked list, rather than the number of elements in the linked list. As mentioned in the last section when implementing Java dynamic array, most interfaces of the linked list are consistent with dynamic array. One of the reasons for the longevity of the Java language is the ability to write maintainable code in a statically compiled language that promotes OCP, interfaces, and abstractions.

Here the List is consistent with the method and attribute extraction and dynamic array into the List interface and abstract class AbstractList, draw the class diagram:

Properties and methods defined in the List interface

1. Attributes:

int ELEMENT_NOT_FOUND = -1; — Check the return flag of no element

2. Interface method:

int size();Query the number of current linked list elements
boolean isEmpty();Check whether the linked list is empty
E set(int index, E element);— Sets the element at index position
E get(int index);— Gets the element at index
boolean contains(E element);— Contains element or not
int indexOf(E element);View the index of the element
void add(E element);Add elements to the tail
void add(int index, E element);Insert an element at index
E remove(int index);— Drop the element at index
void clear();Clear all elements

AbstractListProperties and methods defined by an abstract class

Abstract class AbstractList implements common methods, while other methods are implemented in LinkedList or DynamicArray. The benefits of this approach are improved code reuse and maintainability

1. Attributes:

protected int size; — Check the return flag of no element

2, Abstract class method:

int size();Query the number of current linked list elements
boolean isEmpty();Check whether the linked list is empty
boolean contains(E element);— Contains element or not
void add(E element);Add elements to the tail
protected void outOfBounds(int index)Illegal index access throws an exception
protected void rangeCheck(int index)— Index check function
protected void rangeCheckForAdd(int index) Add an index check function to the element

LinkedListProperties and methods defined by linked list classes

1, properties,

private Node<E> first;Defines the first node of the list, pointing to the first element of the list

2, methods,

E set(int index, E element);— Sets the element at index position
E get(int index);— Gets the element at index
int indexOf(E element);View the index of the element
void add(int index, E element);Insert an element at index
E remove(int index);— Drop the element at index
public E remove(E element);— Removes the specified element
void clear();Clear all elements
private Node<E> node(int index)Get the node object corresponding to the index position

After the completion of the design, is the specific method coding implementation, some simple methods here will not explain, annotations have been very clear, here to talk about some key methods

List initialization

Private Node

first defined in LinkedList; And AbstractList protected int size; Is the first node that makes up the list. Before the element node is added, its value looks like this:

Void add(int index, E element); When we add an element to a specified index, we need to find the Node before the index, and then modify the pointer to complete the operation of adding an element Node, and extract the operation into a private Node

Node (int index) method.

If size is 0, first refers to null. If size is not 0, first refers to the first node of the list.

/** * get the node object * corresponding to the index position@param index
  * @return* /
private Node<E> node(int index){
    rangeCheck(index);

    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}
Copy the code

To find the node at the index position, starting from first, we need next to find the index times. For example, we find the node with index 2, and the process is as follows:

Ok, so I’m going to go back to add, and what I do is I point the new node to the index node that I want to insert, I change the index of the node that preceded it, I point it to the new node, and then size++, depending on whether or not index = 0 is true, because index = 0, there’s no element node, Only the address of the first node is referenced.

/** * inserts an element ** at index position@param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    if (index == 0){
        first = new Node<>(element,first);
    }else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element,prev.next);
    }
    size++;
}
Copy the code

If the index! Prev = Node (index – 1); Next = new Node<>(Element,prev.next); , draw a picture to explain:

Size = 0,index = 0, size = 0,index = 0

Deleting nodes is similar to adding nodes, so I’m not going to draw a picture here. After reading the above analysis of several key methods, I believe that the structure of the above linked list will not have doubts

The complete code

The List interface

public interface List<E> {

    // check the return flag of no element
    int ELEMENT_NOT_FOUND = -1;

    /** * Number of elements *@return* /
    int size(a);

    /** * is null *@return* /
    boolean isEmpty(a);

    /** * Sets the element * at index position@param index
     * @param element
     * @returnThe original element ֵ */
    E set(int index, E element);

    /** * gets the element * at index position@param index
     * @return* /
    E get(int index);

    /** * Whether to contain an element *@param element
     * @return* /
    boolean contains(E element);

    /** * View the index of the element *@param element
     * @return* /
    int indexOf(E element);

    /** * add the element to the end *@param element
     */
    void add(E element);


    /** * inserts an element * at index position@param index
     * @param element
     */
    void add(int index, E element);

    /** * delete element * at index position@param index
     * @return* /
    E remove(int index);

    /** * removes the specified element *@param element
     * @return* /
    public E remove(E element);

    /** * clears all elements */
    void clear(a);
}
Copy the code

Abstract superclass design

Abstract parent classAbstractListIs the interfaceListThe implementation of the

public abstract class AbstractList<E> implements List<E>  {
    /** * The number of elements */
    protected int size;

    /** * Number of elements *@return* /
    public int size(a) {
        return size;
    }

    /** * is null *@return* /
    public boolean isEmpty(a) {
        return size == 0;
    }

    /** * Whether to contain an element *@param element
     * @return* /
    public boolean contains(E element) {
        returnindexOf(element) ! = ELEMENT_NOT_FOUND; }/** * add the element to the end *@param element
     */
    public void add(E element) {
        add(size, element);
    }

    /** * Invalid index access array exception *@param index
     */
    protected void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    /** * index check function *@param index
     */
    protected void rangeCheck(int index) {
        if (index < 0|| index >= size) { outOfBounds(index); }}/** * array adds element index check function *@param index
     */
    protected void rangeCheckForAdd(int index) {
        //index > size, the element can be added to the array size, that is, the next storage location at the end of the array
        if (index < 0|| index > size) { outOfBounds(index); }}}Copy the code

List –`LinkedList`

public class LinkedList<E> extends AbstractList<E> {

    /** * defines the first node of the list, pointing to the first element */
    private Node<E> first;

    /** * defines the Node class, which contains elements and an address reference to the next Node@param <E>
     */
    private static class Node<E>{
        E element;
        Node<E> next;

        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next; }}/** * sets the element ** at index position@param index
     * @param element
     * @returnThe original element ֵ */
    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    /** * gets the element ** at index position@param index
     * @return* /
    @Override
    public E get(int index) {
        return node(index).element;
    }

    /** * View the index of the element **@param element
     * @return* /
    @Override
    public int indexOf(E element) {
        // If the element is empty
        if (element == null){
            Node<E> node = first;
            for (int i = 0; i < size; i++){if (node.element == null) returni; node = node.next; }}else {
            // The element is not empty
            Node<E> node = first;
            for (int i = 0; i < size; i++){if (element.equals(node.element)) returni; node = node.next; }}// There is no such element
        return ELEMENT_NOT_FOUND;
    }

    /** * inserts an element ** at index position@param index
     * @param element
     */
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        if (index == 0){
            first = new Node<>(element,first);
        }else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element,prev.next);
        }
        size++;
    }

    /** * delete the element ** at index position@param index
     * @return* /
    @Override
    public E remove(int index) {
        rangeCheck(index);

        Node<E> node =first;
        if (index == 0){
            first = first.next;
        }else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

    /** * removes the specified element **@param element
     * @return* /
    @Override
    public E remove(E element) {
        return remove(indexOf(element));
    }

    /** * clears all elements */
    @Override
    public void clear(a) {
        size = 0;
        first =null;
    }

    /** * get the node object * corresponding to the index position@param index
     * @return* /
    private Node<E> node(int index){
        rangeCheck(index);

        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public String toString(a) {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append("[");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if(i ! =0) {
                string.append(",");
            }

            string.append(node.element);

            node = node.next;
        }
        string.append("]");
        returnstring.toString(); }}Copy the code

Virtual header

concept

Improved linked lists: Create linked lists with virtual headers

Why: Sometimes you can add a virtual header (no data storage) to the front of the code to make it more streamlined and to unify the processing logic of all nodes.

Class diagram relationships: In terms of inheritance and abstract interface design, Virtual_LinkedList and LinkedList remain unchanged

The structure design

Structure of linked lists with virtual heads

Virtual_LinkedListProperties and methods defined by linked list classes

1, properties,

private Node<E> first;Defines the first node of the list, pointing to the first element of the list

2, methods,

Public Virtual_LinkedList() — constructor that initializes the creation of virtual headers
E set(int index, E element); — Sets the element at index position
E get(int index); — Gets the element at index
int indexOf(E element); View the index of the element
void add(int index, E element); Insert an element at index
E remove(int index); — Drop the element at index
public E remove(E element); — Removes the specified element
void clear(); Clear all elements
Private Node

Node (int index) — Get the Node object corresponding to the index position

Methods changes of

The first change is to add the constructor public Virtual_LinkedList(), which initializes the creation of virtual headers

/** * constructor to create a virtual header */ regardless of whether there is data
public Virtual_LinkedList(a) {

    first = new Node<>(null.null);
}
Copy the code

Private Node

Node (int index)

The pointer should be changed from first to first.next, so that the pointer still points to the element whose index is 0

/** * get the node object * corresponding to the index position@param index
 * @return* /
private Node<E> node(int index){
    rangeCheck(index);

    Node<E> node = first.next;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}
Copy the code

Public int indexOf(E element) public int indexOf(E element) public int indexOf(E element

/** * View the index of the element **@param element
 * @return* /
@Override
public int indexOf(E element) {
    // If the element is empty
    if (element == null){
        Node<E> node = first.next;
        for (int i = 0; i < size; i++){if (node.element == null) returni; node = node.next; }}else {
        // The element is not empty
        Node<E> node = first.next;
        for (int i = 0; i < size; i++){if (element.equals(node.element)) returni; node = node.next; }}// There is no such element
    return ELEMENT_NOT_FOUND;
}
Copy the code

Void add(int index, E element);

Before we said to add a new node method, is to find the position before the position of the insert index, pointer to changes, but the location of the index is 0, the front there is no element nodes, so this kind of situation is not common, need according to the index = = 0 are divided into two kinds of circumstances, but there is a virtual head node, That makes it universal, and it also simplifies the code, unifying the processing logic of all nodes

/** * inserts an element ** at index position@param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // Index = 0, node(0-1), -1 will not pass the check, but the added logic is the same
    Node<E> prev = (index == 0 ? first : node(index - 1));
    prev.next = new Node<>(element,prev.next);
    size++;
}
Copy the code

5, change the method — E remove(int index); Similarly, the delete method is the same as the add method, unifying the processing logic of all nodes

/** * delete the element ** at index position@param index
 * @return* /
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node;
    Node<E> prev =(index == 0 ? first : node(index - 1));
    node = prev.next;
    prev.next = node.next;
    size--;
    return node.element;
}
Copy the code

Two-way linked list

concept

Previously, we have written one-way linked lists in the above, the disadvantage is relatively obvious, each time to obtain node elements need to start from the beginning node traversal. Using bidirectional linked list can effectively improve the comprehensive performance of linked list

Class diagram relationship:In terms of inheritance relation and abstract interface design,Both_LinkedListwithLinkedListSame, unchanged

Bidirectional linked list design

/** * defines a pointer to the end of the list, pointing to the end element */
private Node<E> last;

/** * defines the Node class, which contains elements and an address reference to the next Node@param <E>
 */
private static class Node<E>{
    E element;
    Node<E> prev;
    Node<E> next;

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

Methods changes of

Private Node

Node (int index)

The node method is a one-way list, so it starts from the beginning. Now it is a two-way list, which determines the direction of the list based on the index position in the middle node

/** * get the node object * corresponding to the index position@param index
 * @return* /
private Node<E> node(int index){
    rangeCheck(index);

    // If the element is in the first half of the list
    if (index < (size >> 1)) {
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    } else {
    // If the element is at the bottom of the list
        Node<E> node = last;
        for (int i = size - 1; i > index; i--) {
            node = node.prev;
        }
        returnnode; }}Copy the code

Void add(int index, E element);

/** * inserts an element ** at index position@param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // Add the element to the end
    if (index == size) {
        Node<E> oldLast = last;
        last = new Node<>(oldLast, element, null);
        // This is the first element added to the list
        if (oldLast == null) {
            first = last;
        } else{ oldLast.next = last; }}else {
        Node<E> next = node(index);
        Node<E> prev = next.prev;
        Node<E> node = new Node<>(prev, element, next);
        next.prev = node;
        //index == 0, add first
        if (prev == null) {
            first = node;
        } else {
            prev.next = node;
        }
    }
    size++;
}
Copy the code

Insert index == 0 at the head and index == size at the tail

1. Insert the middle position

2. Insert the head position

3. Insert the tail position

The important thing to note here is that if the bidirectional list is empty, then the first element is inserted at the end

3, change the method — E remove(int index);

In fact, removing node elements is the same as adding elements above. Here, I will not draw diagrams to explain. If you do not understand the code, you can look at the structure diagram of the bidirectional linked list, read or DeBug it again

/** * delete the element ** at index position@param index
 * @return* /
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = node(index);
    Node<E> prev = node.prev;
    Node<E> next = node.next;

    // index == 0
    if (prev == null){
        first = next;
    }else {
        prev.next = next;
    }
    // index == size - 1 
    if (next == null){
        last = prev;
    }else {
        next.prev = prev;
    }
    size--;
    return node.element;
    
}
Copy the code

Circular linked list

Unidirectional cyclic linked lists

Structural design:

Method changes:

Void add(int index, E element);

Index == 0 “size == 0” index == 0 “size == 0” index == 0 “size == 0” index == 0

/** * inserts an element ** at index position@param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    if (index == 0){
        first = new Node<>(element,first);
        Node<E> last =(size == 0)? first : node(size -1);
        last.next = first;

    }else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element,prev.next);
    }
    size++;
}
Copy the code

When size == 0, the add operation looks like the following, and when there is only one node in the linked list, it is also the point to delete

Public E remove(int index);

/** * delete the element ** at index position@param index
 * @return* /
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = first;
    if (index == 0) {
        if (size == 1) {
            first = null;
        } else {
            Node<E> last = node(size - 1); first = first.next; last.next = first; }}else {
        Node<E> prev = node(index - 1);
        node = prev.next;
        prev.next = node.next;
    }
    size--;
    return node.element;
}
Copy the code

Bidirectional circular linked lists

Structural design:

Method changes:

Void add(int index, E element);

In fact, the bidirectional list is just based on the double-linked list, the next of the tail points to the header, and the prev of the header points to the tail, so a lot of things don’t change. We just need to worry about adding and deleting

/** * inserts an element ** at index position@param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);

    // Add the element to the end
    if (index == size) {
        Node<E> oldLast = last;
        last = new Node<>(oldLast, element, first);
        // This is the first element added to the list
        if (oldLast == null) {
            first = last;
            first.next = first;
            first.prev = first;
        } else{ oldLast.next = last; first.prev = last; }}else {
        Node<E> next = node(index);
        Node<E> prev = next.prev;
        Node<E> node = new Node<>(prev, element, next);
        next.prev = node;
        prev.next = node;
        //index == 0, add first
        if (index == 0) {
            first = node;
        }
    }
    size++;
}
Copy the code

Note that when size == 0, the insert header pointer points to the following

Public E remove(int index);

/** * delete the element ** at index position@param index
 * @return* /
@Override
public E remove(int index) {
    rangeCheck(index);

    Node<E> node = first;
    if (size == 1){
        first = null;
        last = null;
    }else {
        node = node(index);
        Node<E> prev = node.prev;
        Node<E> next = node.next;
        prev.next = next;
        next.prev = prev;

        // index == 0
        if (node == first){
            first = next;
        }
        // index == size - 1
        if (node == last){
            last = prev;
        }
    }
    size--;
    return node.element;

}
Copy the code

summary

One-way linked list VS bidirectional linked list

A rough comparison of the number of deleted operations:

In contrast, the operation of bidirectional linked lists is cut in half, but the memory footprint is also increased

Dynamic arrays VS linked lists

1. Dynamic array: the number of opening and destroying memory space is relatively small, but may cause memory space waste (can be solved by reducing the size) 2. Bidirectional linked list: the number of opening and destroying memory space is relatively large, but will not cause memory space waste

Application Scenarios:

If you frequently add or delete operations in the tail, dynamic array and bidirectional linked list can be selected
If the header is frequently added or deleted, you are advised to use a bidirectional linked list
If there are frequent add and delete operations (in any location), it is recommended to use bidirectional linked lists
If there are frequent query operations (random access operations), dynamic arrays are recommended

The statement

Personal ability is limited, have incorrect place, also please correct

The article is original, welcome to reprint, just indicate the source

The code for this article has been uploadedgithub, welcomestar

GitHubaddress

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.

Hands-on coding – Linked lists (Java implementation)

preface

concept

Design of linked lists

The complete code

The List interface

Abstract superclass design

List –`LinkedList`

Virtual header

concept

The structure design

Methods changes of

Two-way linked list

concept

Bidirectional linked list design

Methods changes of

Circular linked list

Unidirectional cyclic linked lists

Bidirectional circular linked lists

summary

One-way linked list VS bidirectional linked list

Dynamic arrays VS linked lists

The statement

Hands-on coding – Linked lists (Java implementation)

preface

concept

Design of linked lists

The complete code

The List interface

Abstract superclass design

List –LinkedList

Virtual header

concept

The structure design

Methods changes of

Two-way linked list

concept

Bidirectional linked list design

Methods changes of

Circular linked list

Unidirectional cyclic linked lists

Bidirectional circular linked lists

summary

One-way linked list VS bidirectional linked list

Dynamic arrays VS linked lists

The statement

Related Posts

MySQL database Sharding database Sharding database

Simple dozens of lines of code to achieve TCP communication

Create a Spring Boot with Eclipse (create and configure controller)

List –`LinkedList`