Data structures and algorithms (2): linked lists

This is a study note on Data Structures and Algorithms (season 1), using the JAVA language

Dynamic arrays have the obvious drawback that they can be a huge waste of memory. Linked lists can claim as much memory as they can

A, list

Linked lists are a kind ofChain storeThe memory addresses of all elements are not necessarily contiguous

Second, the design of linked list

Create a classLinkedList, used to manage linked list data, wheresizeProperty records the amount of data stored,firstProperty refers to the first part of the list0An element
Creating a private classNode, in which theelementAttributes are used to store elements,nextProperty is used to point to the next node in the list

public class LinkedList<E> {
    private int size;
    private Node<E> first;
    // Private class, a node in a linked list
    private class Node<E> {
        E element;
        Node<E> next;
        // constructor
        public Node(E element, Node<E> next) {
            this.element = element;
            this.next = next; }}}Copy the code

3. Interface design of linked list

Like dynamic arrays, linked lists need to be added, deleted, modified, and checked

// The number of elements
int size(a); 
// Whether it is empty
boolean isEmpty(a);
// Whether to contain an element
boolean contains(E element); 
// Add the element to the end
void add(E element); 
// Return the element corresponding to the index position
E get(int index); 
// Set the element at index position
E set(int index, E element); 
// Add an element to index
void add(int index, E element); 
// Delete the element corresponding to the index position
E remove(int index); 
// View the position of the element
int indexOf(E element); 
// Clear all elements
void clear(a); 
Copy the code

Realization of linked list interface

1, index out of bounds judgment

When manipulating linked list data, you need to prevent index transgressions and program exceptions
When looking up and dropping data, you need to check the range of indexes0 to size 1So the method is as follows

private void rangeCheck(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:"+ size); }}Copy the code

When inserting data, you need to check the index range because you can add data to the end of all data0 to sizebetween

private void rangeCheckForSize(int index) {
    if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:"+ size); }}Copy the code

2. Search for the specified node based on the index

Because the data in the linked list is stored in nodes, the corresponding nodes need to be found when the data is manipulated
We can implement a method to find the specified node by index

private Node<E> node(int index) {
    rangeCheck(index);
    // The header is the node that first points to
    Node<E> node = first;
    // Traverse the index to find the corresponding node
    for (int i = 0; i < index; i++) {
    	node = node.next;
    }
    return node;
}
Copy the code

3. Add data

To add data, you need to create a node to store the data, and splice the node to the end of the last node, and thensizeadd1
Two cases
- First: the current linked list has no data, and the new node is concatenated to first
- Second: the current list has data, and the new node splices to the last node

public void add(E element) {
    // When first equals null, there is no node for this event, so first refers to the new node
    if (first == null) {
    	first = new Node<E>(element, null);
    }else {
    	Fitst = fitST; fitST = fitST; fitST = fitST; fitST = fitST; fitST = fitST
        Node<E> node = node(size - 1);
        node.next = new Node<E>(element, null);
    }
    size++;
}
Copy the code

4. Insert elements

To insert a linked list, you simply create a new node to hold the element and then insert it at the specified location
Two cases
- First: insert to position 0, need to use first to point to the new node
- Second: insert to non-zero position, directly find the previous node for processing

public void add(int index, E element) {
    // Check if the index is out of bounds
    rangeCheckForSize(index);
    // when inserted at position 0
    if (index == 0) {
        // First points to the new node, and next points to the node first pointed to before
        first = new Node<E>(element, first.next);
    }else {
        // Find the node before the specified location
        Node<E> prev = node(index - 1);
        // Next of the previous node points to the new node, and next of the new node points to the node pointed to before prev
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}
Copy the code

The method for adding elements can be abbreviated

public void add(E element) {
    // The element is added to the size position, that is, to the last
    add(size, element);
}
Copy the code

5. Delete elements

Delete the element, find the node in front of the specified node, and then point directly to the next node that needs to be deletedsizeReduction of1
Two cases
- First: delete the 0th element, using first to point to the first node
- The second option: delete the element with a non-zero index, find the previous node, and then point directly to the next node

public E remove(int index) {
    // Check if the index is out of bounds
    rangeCheck(index);
    // Record the node to be deleted
    Node<E> old = first;
    // When the 0th element is deleted, point first's next to the node whose index is' 1 '
    if (index == 0) {
        first = first.next;
    }else {
        // Find the previous element
        Node<E> prev = node(index - 1);
        // Record the node to be deleted
        old = prev.next;
        // Point the next of the prev to the next node where the node needs to be removed
        prev.next = old.next;
    }
    // size-1
    size--;
    // Returns the deleted element
    return old.element;
}
Copy the code

6. Empty elements

Empty the elements directly intofirstPoint to thenullOk, in the meantimesizeSet to0

public void clear(a) {
    first = null;
    size = 0;
}
Copy the code

7. Modify elements

Modify the element, find the corresponding node, directly modify the element

public E set(int index, E element) {// Find the corresponding node <E> node = node(index); E old = node.element; // Overwrite element node.element = element; // Return the old elementreturn old;
}
Copy the code

8. Find elements

Find the element, directly find the corresponding node, take out the element

public E get(int index) {
    // The node method determines whether the index is out of bounds
    return node(index).element;
}
Copy the code

Find the element index

To find the index of the specified element, you need to traverse all nodes until the element corresponding to the node is equal to the execution element
Because the elements can benull, so it needs to be handled in two cases

private static final int ELEMENT_ON_FOUND = -1;
public int indexOf(E element) {
    // Fetch the header
    Node<E> node = first;
    // When element is null
    if (element == null) {
        // Walk through the node, find the node stored as null, return the index
        for (int i = 0; i < size; i++) {
            if (node.element == null) returni; node = node.next; }}else {
        for (int i = 0; i < size; i++) {
            // Iterate over the node to find the node whose stored element is equal to the specified element, and return the index
            if (element.equals(node.element)) returni; node = node.next; }}// ELEMENT_ON_FOUND is not found
    return ELEMENT_ON_FOUND;
 }
Copy the code

Get the number of linked list stored elements

Gets the number of linked list stored elements, which issizeThe value of the

public int size(a) {
    return size;
}
Copy the code

11. Whether the list is empty

Whether the list is empty or not is just a matter of judgmentsizeWhether is equal to the0Can be

public boolean isEmpty(a) {
    return size == 0;
}
Copy the code

12. Determine if the element exists

To check whether an element exists, you only need to check whether the element index isELEMENT_ON_FOUNDCan be

public boolean contains(E element) {
    returnindexOf(element) ! = ELEMENT_ON_FOUND; }Copy the code

Print the data stored in the linked list

I just have to rewritetoStringMethods can be

@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("]");
    return string.toString();
}
Copy the code

Data structures and algorithms (2): linked lists

A, list

Second, the design of linked list

3. Interface design of linked list

Realization of linked list interface

1, index out of bounds judgment

2. Search for the specified node based on the index

3. Add data

4. Insert elements

5. Delete elements

6. Empty elements

7. Modify elements

8. Find elements

Find the element index

Get the number of linked list stored elements

11. Whether the list is empty

12. Determine if the element exists

Print the data stored in the linked list

Related Posts

Java Design Pattern — Singleton Pattern

Installation and use of HomeBrew and HomeBrew Cask

Ali Cloud heterogeneous computing team at nvidia 2018 GTC Conference