Linked list data structure (Linked List)

What is a linked list (Linked List)?

A Linked List is a sequence of data structures that are connected through links (links). Simply put, the Linked List is a data structure consisting of a group of nodes (nodes) forming a string. Each node contains data at that node and references the next node in the string.

The linked list is the second most commonly used data structure after the array. Here are the basic concepts related to Link List:

Link : each link of a linked List can store a data called an element.

Next : Each link of a linked list contains a link to the next link called Next.

First : A linked list includes links to the first link called First.

Performing Linked List (Linked List)

The linked list can be represented as a sequence of nodes (nodes). Each node will point to the next node.

Linked list data structure (Linked List) Picture 1

Here are some points to remember about Link list:

The linked list contains a link element called First.

Each link has a data field and a link field called Next.

Each link is linked to the next link by using its next link.

The last link has a link that is null to mark the end of the list.

Types of Linked Lists (Linked List)

Here are the various types of Linked Lists:

Simple linked list (Simple Linked List) : only browse elements in the previous direction.

Doubly Linked List : elements can be browsed in the forward or backward direction.

Round list (Circular Linked List) : the last element contains the link of the first element such as next and the first element has a link to the last element as prev.

Basic activities on the Linked List

Here are some basic operations that can be performed by a linked list:

Insert operation : add an element at the top of the linked list.

Delete operation (first element) : delete an element at the top of the linked list.

Display : display the entire list.

Search activity : search for an element by using the key provided.

Delete operation (by using the key) : delete an element by using the key provided.

Insert operation in linked list

Adding a new node to the linked list is not just a simple extra operation as in other data structures (because we have data and links). We will learn through the diagram below. First, create a node using the same structure and find the location to insert this node.

Linked list data structure (Linked List) Picture 2

Suppose we need to insert a node B between node A (left) and C (right button). Therefore: B.next points to C.

 NewNode.next -> RightNode; 

The illustration is as follows:

Linked list data structure (Linked List) Picture 3

Now, the next button on the left will return to the new node.

Linked list data structure (Linked List) Picture 4

The above process will place the new button between the two buttons. Then the new list will look like this:

Linked list data structure (Linked List) Picture 5

The same steps will be taken if the button is inserted at the top of the linked list. While placing a button at the end of the list, the second button from the last node of the list will point to the new node and the new node will point to NULL.

To learn how to deploy the algorithm in C language, please visit the List of C's links.

Delete operation in the Linked List

Deleting operations in the Linked List is also more complicated in other data structures. First we need to locate the node to be deleted using search algorithms.

Linked list data structure (Linked List) Picture 6

Now, the left button (prev) of the button to delete should point to the next button (next) of the node to be deleted.

 LeftNode.next -> TargetNode.next; 

Linked list data structure (Linked List) Picture 7

This process will delete the link pointing to the button to be deleted. Now we will delete what the delete button is pointing to.

 TargetNode.next -> NULL; 

Linked list data structure (Linked List) Picture 8

If you need to use this deleted button, you can keep them in memory, otherwise you can completely remove it from memory.

Linked list data structure (Linked List) Picture 9

To learn how to implement the algorithm in C language, please visit the List of C's links.

Reverse operation List link

With this activity, you need to be careful. We need to make the first node (head) point to the last node and reverse the entire linked list.

Linked list data structure (Linked List) Picture 10

First, we browse to the end of the list. This button will point to NULL. Now what to do is to make this last node point to its forward node.

Linked list data structure (Linked List) Picture 11

We must ensure that this last node will not be lost, so we will use some temporary nodes (temp nodes - like temporary intermediate variables to store values). Next, we will make each node on the left point to their left button.

Linked list data structure (Linked List) Picture 12

After that, the first node after the head node will point to NULL.

Linked list data structure (Linked List) Picture 13

We will make the head node point to the new first node by using temporary buttons.

Linked list data structure (Linked List) Picture 14

Now the linked list has been reversed.

To learn how to implement the algorithm in C language, please visit the List of C's links.

According to Tutorialspoint

Previous article: Theorem mechanic algorithm (Master Theorem)

Next lesson: Data structure and algorithm Double link list