This is a series of articles, each with the source code address at the end. The goal is to get a general idea of common data structures and Java collections by simulating a simple implementation of the collections framework. Of course, the implementation is not as complex or as powerful as the Java collection implementation, but you can peek into some underlying common principles through these simple implementations.
Storage structure of single linked list
A singly linked list is a system that stores data in a number of storage units scattered over addresses. Data elements that are logically adjacent may not be physically adjacent. Therefore, for each data element itself, in addition to storing its own element value, you need an address that points to the following element. The structure of the data elements is as follows:
The above data element structure is usually called a node, and a data element is called a node. It is composed ofData fieldsandThe address fieldComposed of, wherein,dataStores the values of the data elements themselves, called data fields;nextThe address that stores the succeeding element, called the address domain. The nodes are connected by their address fields. The structure of a singly linked list is as follows:
In the single linked list above,headIs the address of the first node of the linked list, called the head of the list; The address domain of the last node isnullwith^Indicates that there is no node after that. fromheadTo start, you can traverse each node in a single linked list by following the list.
Realization of single linked list
Singly linked lists are linked by nodes, so singly linked lists can be implemented by defining singly linked list node classes and singly linked list classes.
1. Define single-linked list node classes
The single-linked list Node class is defined as follows:
package org.light4j.dataStructure.linearList.linkList; /** * @author longjiazuo */ public class Node<E> {public E data; Public Node<E> next; Public Node(E data, Node<E> next) {this.data = data; this.next = next; } public Node(E data) { this(data, null); } public Node() { this(null, null); }}Copy the codeCode explanation:
The Node class has two member variables. Data represents the data domain of the Node and stores the value of the data element itself. The data type is generic E. Next represents the address field of the node, which stores the addresses of subsequent nodes of the data element.
2.
NodeClass representing a node in the linked list, throughnextAddress fields link nodes together,p.next=q, as shown in the figure below:
2. Define single-linked list classes
The SinglyLinkedList class is defined as follows, with the head member variable representing the head of the SinglyLinkedList.
package org.light4j.dataStructure.linearList.linkList; import org.light4j.dataStructure.linearList.LList; public class SinglyLinkedList<E> implements LList<E> { protected Node<E> head; /** * public SinglyLinkedList() {this.head = null; } @param head */ public SinglyLinkedList(Node<E> head) {this.head = head; }}Copy the codeCode explanation:
① The SinglyLinkedList class implements the interface LList, so it must implement the related methods of the interface. The specific implementation will be split listed below.
(2) We define two constructors, the default constructor, which specifies that the head of a single list is null. Another constructor can specify the head of a singly linked list.
3. Check whether the single-linked list is empty
*/ @override public Boolean isEmpty() {return this.head == null; }Copy the code4. Find the length of a single list
*/ @override public int length() {Node<E> p = this.head; Int I = 0; while (p ! = null) {// if the list does not end i++; p = p.next; } return I; }Copy the codeCode explanation:
1.Finding the length of a single linked list requires traversing a single linked list. To traverse a single linked list means to visit each node in the single linked list from the first node along the direction of the node chain, and each node can be accessed only once. The traversal process is shown in the figure below:
2.The head of a single linked list should not be changed while iterating through it, so you need to define a variablepPoints to the current node,pfromheadStarting with the node pointed to, each node is visited in turn until the last node, thus completing a traversal operation.
5. Obtain the object at the specified index in the single-linked list
@override public E get(int index) {Node<E> p = this.head; int i = 0; while (p ! = null && i < index) { i++; p = p.next; } if (p ! = null) { return p.data; } return null; }Copy the codeCode explanation:
(1) To obtain the object at the specified index of a single linked list, you need to traverse the single linked list to find the index, which is actually a single linked list traversal operation.
6. Assign to the object at the index specified for the singly linked list
@override public E set(int element, E element) {if (this.head! = null && index >= 0 && element ! = null) { Node<E> p = this.head; int i = 0; while (p ! = null && i < index) { i++; p = p.next; } if (p ! = null) { E old = p.data; p.data = element; return old; }} return null; // Return null}Copy the code① To specify an index assignment for a single linked list, first traverse the single linked list to find the index, and then assign, in fact, the single linked list traversal operation.
7. Insertion of singly linked lists
Insertion into a single linked list is very convenient. You only need to change the link relationship between nodes, and you do not need to move elements. The code is as follows:
*/ @override public Boolean add(int index, int index); E element) { if (element == null) { return false; } Node<E> q = new Node<E>(element); / / create to insert nodes if (this. Head = = null | | index < = 0) {/ / at the back of the head node insert q.n ext = this. The head; this.head = q; } else {// Insert Node<E> p = this.head; int i = 0; while (p.next ! = null &&i < index - 1) { p = p.next; } q.next = p.next; // insert q after p; } return true; } @override public Boolean add(E element) {return add(integer.max_value, element); }Copy the codeCode explanation:
Insert a node in a single linked list, according to the insertion position can be divided into empty table insert, head insert, middle insert, tail insert four cases.
① Empty table insert and head insert
1.1 Empty table insert
An empty table insert is when a single linked list is empty and a node is inserted,headPoints to the inserted node. As shown below:
1.2 insert
Header insertion refers to if the single-linked list is not empty, inheadInsert nodes before nodesqAfter insertingqThe node becomes the first node in a single linked list,headThe node points to the node. As shown below:
Both inserts change the head of a singly linked listheadPointing to. The following statement:
if(head==null){
head=new Node(x);
}else{
Node q = new Node(x);
q.next=head;
head=q;
}② Middle insertion/tail insertion
2.1 Intermediate Insertion
Intermediate insertion refers to inserting the node to be inserted after a node in the middle of a non-empty list. As shown below:
2.2 the tail insertion
Tail insertion refers to inserting the node to be inserted after the current tail node of a single linked list to become a new tail node. As shown below:
These two inserts do not change the head of a singly linked listheadPointing to. setpPoints to a node in a non-empty list (or possibly the last node in the list), wherepInsert after nodeqThe statement of the node is as follows:
Node q = new Node(x);
q.next=p.next;
p.next=q;
8. Delete single linked lists
Deleting a node in a singly linked list requires only changing some links, and does not require moving node data elements. According to the location of the element node to be deleted, it can be divided into head deletion, middle deletion and tail deletion. The code is as follows:
@override public E remove(int index) {E old = null; if (this.head ! = null &&index >= 0) {if (index == 0) {// Delete old = this.head.data; this.head = this.head.next; return old; } else {// Delete Node<E> p = this.head; int i = 0; while (p ! = null && I < index - 1) {// Locate the precursor node I ++ of the node to be deleted; p = p.next; } if (p ! = null && p.next ! = null) { old = p.next.data; P.ext = (p.ext).next; }}} return old; }Copy the codeCode explanation:
1) first delete
Header deletion is shown below:
To delete the first node of a singly linked list, enableheadNodes point to subsequent nodes. The implementation statement is as follows:
head=head.next;
Singly linked list if there is only one node, then the singly linked list will be empty after the node is deleted, i.e., after the above statement is executed,headintonull.② Middle delete or tail delete
Intermediate or final deletion is as shown below:
Intermediate deletion refers to the deletion of a node in the middle of the list, and tail deletion refers to the deletion of the last node of the list. setpPoint to a node other than the last node in the singly linked list, deletepThe following statement for the successor node of:
if(p.next ! = null){
p.next = p.next.next;
}
JavaGarbage collection automatically frees objects that are no longer used and reclaims their memory space, so we don’t need to write code that frees the storage unit of the deleted node.
9. Clear single-linked lists
@override public void clear() {this.head = null; }Copy the codeCode explanation:
To clear a single linked list, set the head of the single linked list to NULL.
10. Rewrite thetoString()methods
@override public String toString() {// Return all elements. String STR = "("; Node<E> p = this.head; while (p ! = null) { str += p.data.toString(); p = p.next; if (p ! = null) { str += ", "; } } return str + ")"; }Copy the codeTest three.
The test code is shown below:
package org.light4j.dataStructure.linearList.linkList; import org.light4j.dataStructure.linearList.LList; public class Test { public static void main(String[] args) { LList<String> linkedList = new SinglyLinkedList<String>(); // add A linkedlist. add("A"); linkedList.add("B"); linkedList.add("C"); System.out.println(" + linkedlist.length ()); }}Copy the codeThe operating effect is shown in the figure below:
Four. Single linked list operation efficiency analysis
Single linked list is a sequential access structure, not a random access structure, so to access a single linked list node, must start from the head node along the direction of the list node by node search, so get() and set() method time complexity is O(n). The isEmpty() method’s time complexity is O(1); The length() method traverses the entire list, so the time complexity is O(n).
Inserting a node after a specified node in a singly linked list is very convenient, and the time complexity is O(1). If you need to specify the singly linked list before the specified node insert node, so you need to first find a precursor of a specific node, and then insert the node to the node, this operation need to traverse singly linked lists, the amount of time to be decided according to the position of the insert, the worst is to insert the node in the list in the end, the time complexity is O (n).
Deleting a specified node in a singly linked list also requires a search for its precursor starting at head, in the worst-case order of O(n) time.
To insert and delete a single linked list, you do not need to move a node, just change the link of the node. Storage space of a single linked list is dynamically applied for and released during insertion and deletion. Storage space of a single linked list does not need to be applied for in advance. In this way, space expansion and element replication are avoided due to insufficient storage space of a single linked list, improving operation efficiency and storage space utilization.
In addition, some operations can be more efficient if some member variables are added to a single linked list. For example, to increment the member variable n to indicate the length of a single list, n++ is performed simultaneously when an element is inserted; When an element is deleted and n– is performed simultaneously, the length() method’s time complexity is O(1). Similarly, if the member variable rear is added as the tail node of the singly linked list, pointing to the last node of the singly linked list, the time complexity of the insertion operation at the end of the singly linked list is O(1).
Five. Source code examples
Github Address: Click to view code cloud address: click to view
exceptional
Welcome to follow the life designer’s wechat public account
longjiazuoA
Self implementation collection framework (three): single linked list implementation