Singly Linked List Data Structure
A singly linked list is a data structure used in computer programming to store a collection of items. It is made up of nodes, each containing some data and a reference to the next node in the list. The first node is called the head of the list, and the last node does not have a reference to any other node, which makes it the tail of the list. Singly-linked lists are commonly used in programming because they allow for easy insertion and removal of nodes, as well as efficient traversal of the list.
The structure of a Singly linked list can be seen in the following image.
The box we can see in the image is called the nodes of the list. the list is made up of nodes. The first node is also known as the head. The last one on the list is known as the tail. each node holds some data and a pointer to the next node.
Why do we need Linked Lists?
Linked lists are needed in computer programming because they overcome some of the limitations of arrays. Arrays are fixed-size, contiguous blocks of memory that can store a collection of data elements of the same type. However, arrays have some limitations that may make them unsuitable for certain tasks:
- Fixed-size: Arrays have a fixed size which means that the number of elements they can store is predetermined. If we want to add more elements to the array, we need to create a new array of larger size and copy the existing elements to the new array. This operation can be time-consuming and memory-intensive.
- Insertion and deletion: Inserting or deleting an element in an array requires shifting all the subsequent elements, which can be time-consuming and inefficient for large arrays.
- Contiguous memory: Arrays require a contiguous block of memory which can be a limitation in some situations where the available memory is fragmented or limited.
Linked lists, on the other hand, are dynamic data structures that allow for the efficient insertion and deletion of elements. They do not require contiguous memory, and their size can be adjusted as needed. Each element in a linked list is a node that contains a data element and a pointer to the next node in the list. This makes linked lists ideal for situations where elements need to be added or removed frequently or where the size of the data structure is unknown or changes over time.
Inserting from the beginning side (Prepend)
bool Linked_list::prepend(int elem)
{
Node *temp = new Node(elem);
if (head == NULL)
{
this->head = temp;
this->tail = temp;
this->size++;
}
else
{
temp->next = head;
this->head = temp;
this->size++;
}
return true;
}
It creates a new node with the given element using the constructor of the Node class.
It checks if the head of the linked list is null. If it is null, it means that the linked list is empty, and the new node becomes both the head and the tail of the list.
If the head is not null, it means that the linked list already contains at least one node. In this case, the next pointer of the new node is set to point to the current head of the list. Then, the head of the list is updated to be the new node.
Finally, the size of the list is incremented, and the function returns true to indicate that the operation was successful.
Inserting from the ending side (Append)
bool Linked_list::append(int elem)
{
Node *temp = new Node(elem);
if (head == NULL)
{
this->head = temp;
this->tail = temp;
this->size++;
}
else
{
this->tail->next = temp;
this->tail = temp;
this->size++;
}
return true;
}
It creates a new node with the given element using the constructor of the Node class.
It checks if the head of the linked list is null. If it is null, it means that the linked list is empty, and the new node becomes both the head and the tail of the list.
If the head is not null, it means that the linked list already contains at least one node. In this case, the next pointer of the current tail node is set to point to the new node, and the new node becomes the new tail of the list.
Finally, the size of the list is incremented, and the function returns true to indicate that the operation was successful.
Inserting at an arbitrary position
bool Linked_list::insert(int pos, int elem)
{
if (pos < 0 || pos > this->size)
return false;
else if (pos == 0)
prepend(elem);
else if (pos == this->size)
append(elem);
else
{
Node *temp = new Node(elem);
Node *current = this->head;
for (int i = 0; i < pos - 1; i++)
current = current->next;
temp->next = current->next;
}
return true;
}
It first checks if the given position is valid. If the position is less than 0 or greater than the size of the list, the function returns false to indicate that the operation failed.
If the position is 0, the function calls the prepend() function to insert the new node at the head of the list.
If the position is equal to the size of the list, the function calls the append() function to insert the new node at the tail of the list.
Otherwise, the function creates a new node with the given element using the constructor of the Node class, and then iterates through the list using a for loop to find the node immediately before the desired position.
Once the correct node is found, the next pointer of the new node is set to point to the next node in the list, and the next pointer of the previous node is updated to point to the new node, effectively inserting the new node at the desired position in the list.
Finally, the size of the list is incremented, and the function returns true to indicate that the operation was successful.
Printing the list of items
void Linked_list::print()
{
Node *current = this->head;
while (current != NULL)
{
cout << current->elem << " -> ";
current = current->next;
}
cout << endl;
}
It starts by creating a pointer to the head node of the list.
It then enters a while loop that continues as long as the pointer is not NULL.
Inside the loop, the function prints out the value of the element stored in the current node, followed by an arrow (->) to indicate that there is another node after this one.
The function then updates the pointer to point to the next node in the list, effectively moving to the next element.
The loop continues until the pointer is NULL, at which point it has reached the end of the list.
Finally, the function prints out a newline character to separate the output from any subsequent output.
Search for a value and delete nodes
int Linked_list::delete_with(int elem)
{
Node *current = this->head;
Node *previous = this->head;
int occurance_count = 0;
while (current != NULL) // Loop until the end of the list
{
if (current->elem == elem) // Check wether the current element is the finding one
{
if (current == this->head)
{
this->head = head->next; // Delete the head node
}
else if (current == this->tail)
{
this->tail = previous; // Delete the tail node
this->tail->next = NULL;
}
else
{
previous->next = current->next; // Delete a middle node
}
delete current;
this->size--;
occurance_count++;
}
else
{
previous = current; // If the current node is not deleted previus
// pointer points to the current node
}
current = current->next;
}
return occurance_count;
}
It starts by creating two pointers, one to the head node of the list and another to the previous node. It also initializes a counter to keep track of the number of occurrences of the given element that are deleted from the list.
It enters a while loop that continues as long as the pointer to the current node is not NULL.
Inside the loop, the function checks whether the current node contains the element to be deleted.
If the current node contains the element to be deleted, the function checks whether the current node is the head or tail node of the list. If it is the head node, the function updates the head pointer to point to the next node in the list. If it is the tail node, the function updates the tail pointer to point to the previous node and sets the next pointer of the new tail node to NULL. If it is a middle node, the function updates the next pointer of the previous node to point to the node after the current node, effectively skipping over the current node and removing it from the list.
After deleting the node, the function decrements the size of the list, increments the counter of occurrences, and deletes the memory allocated for the current node.
If the current node does not contain the element to be deleted, the function updates the previous pointer to point to the current node, effectively moving it forward to one node.
The loop continues until the pointer to the current node is NULL, at which point it has reached the end of the list.
Finally, the function returns the count of occurrences of the element that were deleted from the list.
Limitations and drawbacks of the Singly-linked lists
Sequential access: Unlike arrays, singly linked lists do not provide direct access to individual elements based on their index or position. Instead, to access an element, you have to traverse the list from the beginning until you reach the desired element. This means that singly linked lists are not efficient for operations that require sequential access to a large number of elements.
No random access: Similarly, since singly linked lists don't provide direct access to elements, you can't easily access elements at a specific index. This means that operations such as binary search, which rely on random access to elements, are not efficient on singly linked lists.
Extra memory overhead: Singly linked lists require additional memory to store the pointers that link each node to the next one. This overhead can become significant for very large lists and can impact the performance of the application.
Limited functionality: Singly linked lists only allow traversal in one direction (forward). This means that certain operations, such as reversing the list or finding the last element, require additional logic and may be less efficient than on other data structures.
Insertion and deletion: Although singly linked lists excel at inserting and deleting elements at the beginning of the list, they can be less efficient for inserting or deleting elements in the middle of the list. This is because you need to traverse the list to find the position where you want to insert or delete the element, which can be time-consuming for large lists.
Well explained and interesting cyber security articles and tutorials on the topics such as System exploitation, Web application hacking, exploit development, malwara analysis, Cryptography etc. Let's explorer the awesome world of computer
