The underlying core principle of the LinkedList implemented in this paper is similar to that of the LinkedList in the Java tool library, but the LinkedList in the Java tool library uses a two-way LinkedList, while the one we implemented is a one-way LinkedList.

1, Node Node class, constructor and general function

As shown below, the Node Node class contains elements E, which holds data, and the next Node, which uses generics. The next Node points to the next Node element, which is why it’s called a linked list;

DummyHead represents the virtual head node, and the next element it points to is the real head node. Size indicates the number of elements;

The no-argument constructor initializes the virtual head node with size set to 0.

GetSize returns the number of list elements; IsEmpty returns whether the list isEmpty;

Public class LinkedList<E> {//Node Node class private class Node{public class E E; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null, null); } @Override public String toString(){ return e.toString(); }} private Node dummyHead; private int size; public LinkedList(){ dummyHead = new Node(); size = 0; } public int getSize(){return size; } public Boolean isEmpty(){return size == 0; },,}Copy the code

2. Add elements to the list

The add(int index, E E) function adds element E to index index; In fact, we don’t have this requirement in linked lists, we’re just practicing; Find the index node through a for loop and insert a new node into it. Time complexity is O(n);

AddFirst means to add elements to the header, so the time complexity is O(1);

AddLast means to add elements to the end of the list, so the time complexity is O(n); Note here that the time complexity of LinkedList to add elements to the end of the LinkedList in Java util library is O(1), because it maintains a bidirectional LinkedList. Both the head node and the end node have records, so it can insert an element directly from the end node without cycling, so it is O(1) time complexity.

E 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 ++; } public void addFirst(e e){add(0, e); } public void addLast(e e){add(size, e); }Copy the code

3. Get the elements in the list

Get (int index) : get(int index); get(int index) : get(int index); Time complexity is O(n);

GetFirst () means to get the header element, which is also O(1) time;

GetLast () means to obtain the last element of the linked list, which is also O(n) time complexity;

/ / get the list of the first index (0 -) -based location element / / in the list is not a common operation 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; } public E getFirst(){return get(0); } public E getLast(){return get(size-1); }Copy the code

4. Modify and find elements

Set (int index, E E); Similarly, a for loop is used to find the Node corresponding to the index, and then modify the element value.

Contains (E E) returns whether there is an element E in the list, traverses the list through a while loop, returns true if it finds it, and false if it does not find it.

Public void set(int index, 0); public void set(int index, 0); 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; E 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

5. Remove elements from the list

Remove (int index) deletes the node at the index. First, find the node to be deleted through a for loop, and then point the next node of the node before the node to be deleted to the next node after the node to be deleted. Finally, the next node of the deleted node points to null for garbage collection.

RemoveFirst () means to remove the head node of the linked list, and the time complexity is O(1).

RemoveLast () indicates that the end node of the linked list is deleted, and the time complexity is O(n).

RemoveElement (E E) removeElement(E E) removeElement(E E) removeElement(E E) removeElement(E E) removeElement(E E)

// 从链表中删除index(0-based)位置的元素, 返回删除的元素
// 在链表中不是一个常用的操作
public E remove(int index){
    if(index < 0 || index >= size)
        throw new IllegalArgumentException("Remove failed. Index is illegal.");

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

    Node deleteNode = prev.next;
    prev.next = deleteNode.next;
    deleteNode.next = null;
    size --;

    return deleteNode.e;
}

// 从链表中删除第一个元素, 返回删除的元素
public E removeFirst(){
    return remove(0);
}

// 从链表中删除最后一个元素, 返回删除的元素
public E removeLast(){
    return remove(size - 1);
}

// 从链表中删除元素e
public void removeElement(E e){

    Node prev = dummyHead;
    while(prev.next != null){
        if(prev.next.e.equals(e))
            break;
        prev = prev.next;
    }

    if(prev.next != null){
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size --;
    }
}
Copy the code

The toString function prints the linked list

Override toString to view list information;

We use StringBuilder to concatenate the linked list node values in turn, and finally convert them to String returns.

@Override public String toString(){ StringBuilder res = new StringBuilder(); Node cur = dummyHead.next; while(cur ! = null){ res.append(cur + "->"); cur = cur.next; } res.append("NULL"); return res.toString(); }Copy the code

7. The complete code of LinkedList is as follows

public class LinkedList<E> { private class Node{ public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null, null); } @Override public String toString(){ return e.toString(); } } private Node dummyHead; private int size; public LinkedList(){ dummyHead = new Node(); size = 0; } public int getSize(){return size; } public Boolean isEmpty(){return size == 0; } // Add a new element e to the index(0-based) position in the list. // Not a common operation in the list. 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 ++; } public void addFirst(e e){add(0, e); } public void addLast(e e){add(size, e); } / / get the list of the first index (0 -) -based location element / / in the list is not a common operation 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; } public E getFirst(){return get(0); } public E getLast(){return get(size-1); } public void set(int index, 0);} public void set(int index, 0); 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; E 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) element from the list, Returns / / delete element in the list is not a common public E remove operation (int index) {if (index < 0 | | index > = size) throw new IllegalArgumentException("Remove failed. Index is illegal."); Node prev = dummyHead; for(int i = 0 ; i < index ; i ++) prev = prev.next; Node deleteNode = prev.next; prev.next = deleteNode.next; deleteNode.next = null; size --; return deleteNode.e; } public E removeFirst(){return remove(0); } public E removeLast(){return remove(size-1); } public void removeElement(e e){Node prev = dummyHead; while(prev.next ! = null){ if(prev.next.e.equals(e)) break; prev = prev.next; } if(prev.next ! = null){ Node delNode = prev.next; prev.next = delNode.next; delNode.next = null; size --; } } @Override public String toString(){ StringBuilder res = new StringBuilder(); Node cur = dummyHead.next; while(cur ! = null){ res.append(cur + "->"); cur = cur.next; } res.append("NULL"); return res.toString(); }}Copy the code