How to implement singly linked list?

This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

The author recently studied “The Beauty of Data Structures and Algorithms”, just take this opportunity to practice while recording their knowledge points. Just get right to it.

What is a linked list

Lists, like arrays, are linear data structures.

The linked list is composed of nodes connected one by one, which are composed of two parts: data domain and pointer domain. Data fields store data, and pointer fields store Pointers (or references) to the next node.

It is the use of Pointers to the next node that allows linked lists to concatenate scattered memory Spaces.

Common linked lists are: single linked lists, circular lists, double linked lists and bidirectional circular lists and so on.

Second, the characteristics of linked lists

Linked list query time complexity O(n), delete insert time complexity O(1) : Because the linked list uses a pointer to the next node, when you want to query a node, you can only traverse from the first node to the target node. But delete and insert only need to point to the new node.
Linked lists require more memory than arrays: in addition to storing data, they also store Pointers to the next node.

Three, single linked list implementation

The implementation of single linked list has two difficulties: one is the operation of inserting nodes, the other is the operation of deleting nodes.

3.1 insert

There are three ways to insert a single linked list. One is to insert the head of the list, the other is to insert the tail of the list, and the third is to directly insert new nodes in the two nodes of the list.

To insert into the head of the list, simply point the pointer to the new node to the head and set the new node to the head.

Insert to the end of the list, you need to traverse the end of the list first, and then point the pointer to the end of the new node.

The two nodes of the linked list are directly inserted into the new node, for example, node P is inserted between node A and node B, node P. next points to node B, and node A. next points to node P.

3.2 delete

Delete a node in the linked list, such as node C. Find the precursor node B of node C and set b.ext = b.ext.next.

3.3 Specific Implementation

/ * * *@author xuls
 * @date2021/11/9 20:49 * Single linked list */
public class SingleLinkedList {
	/** * the node class that stores string data */
	private static class Node{
		private String data;
		private Node next;// point to the next node

		public Node(String data, Node next) {
			this.data = data;
			this.next = next;
		}

		@Override
		public String toString(a) {
			return "Node{" +
					"data='" + data + '\' ' +
					'} '; }}private Node head;/ / head node

	// Insert data into the head of the singly linked list
	public void insertHead(String data){
		Node node = new Node(data, null);
		// If the header is null, insert it directly
		if (head == null){
			head = node;
		}else {
			// Next points to head and set node to headnode.next = head; head = node; }}// Insert data into the end of the single list
	public void insertTail(String data){
		Node node = new Node(data, null);
		// If the header is null, insert it directly
		if (head == null){
			head = node;
		}else {
			Node temp = head;
			// Find the node that points to the next node as null, which is the last node
			while( temp.next ! =null){
				temp = temp.next;
			}
			// point the next node from the last node to the new nodetemp.next = node; }}// Insert data before node
	public void insertBefore(String data,Node node){
		if (node == null) {return;
		}
		// Insert before the header
		if (node == head){
			insertHead(data);
			return;
		}

		// Find the pre-node of the insertion node
		Node before = head;
		while(before ! =null&& before.next ! = node){ before = before.next; }if (before == null) {// Indicates that node nodes are not directly returned in a single linked list
			return;
		}

		Node newNode = new Node(data, null);
		newNode.next = node;
		before.next = newNode;
	}

	// Insert data after node
	public void insertAfter(String data,Node node){
		if (node == null) {return;
		}
		Node newNode = new Node(data, null);
		newNode.next = node.next;
		node.next = newNode;
	}

	// Delete the node
	public void delete(Node node){
		if (node == null || head == null) {return;
		}
		if (node == head){
			head = head.next;
			return;
		}
		// Find the previous node of the deleted node
		Node before = head;
		while(before ! =null&& before.next ! = node){ before = before.next; }if (before == null) {// Delete node is not in the linked list
			return;
		}
		
		before.next = before.next.next;
	}

	// Find the node at index
	public Node find(int index){
		if (head == null || index < 0) {return null;
		}
		
		Node node = head;
		int position = 0;
		while(node ! =null&& position ! = index){ node = node.next; position++; }return node;
	}

	@Override
	public String toString(a) {
		StringBuilder builder = new StringBuilder();
		builder.append("SingleLinkedList：");
		if (head == null){
			builder.append("null");
		}else {
			Node node = head;
			while(node ! =null){
				builder.append(node.data).append("-- >");
				node = node.next;
			}
			builder.append("null");
		}
		returnbuilder.toString(); }}Copy the code

Array or linked list

Arrays and linked lists are common basic data structures, and they are often compared side by side. How do we choose linear data structures?

4.1 Complexity of Random Access, Insert, and Delete Time

	Random access	Delete, insert
An array of	O(1)	O(n)
The list	O(n)	O(1)

4.2 Array storage vs Linked list storage

Arrays require contiguous memory. For example, if you need 99 megabytes of contiguous memory and you don’t have 99 megabytes of contiguous memory, the array creation will fail.

Arrays of contiguous memory space can take advantage of the CPU’s caching mechanism to make data access faster.

Arrays are fixed in size, and although we can achieve dynamic array expansion, frequent data movement is also very time consuming.

Linked lists use Pointers to join discrete memory Spaces together, but this requires extra memory space to store Pointers to the next node. Frequently creating objects in linked lists can also create memory fragmentation.

Summary above according to your needs, specific problem specific analysis.

Portal: How to dynamically expand the array

XDM, use your little hands and comment like, please.

How to implement singly linked list