Overview of Linked List
A linked list is a
fundamental data structure in computer science that represents a linear
collection of elements.
Unlike arrays,
linked lists do not store elements in contiguous memory locations.
Instead, each
element (node) in a linked list contains a data element and a reference (link
or pointer) to the next node in the sequence.
The last node
typically points to null, indicating the end of the list.
key concepts
related to linked lists:
---------------------------------------
Basic Components
of a Linked List:
1. Node:
- A fundamental building block of a linked
list.
- Contains two fields: data and a reference
(or link) to the next node.
2. Head:
- The first node in the linked list.
- Serves as the entry point for accessing
the elements in the list.
3. Tail:
- The last node in the linked list.
- Its "next" reference is usually
set to null.
Types of Linked Lists:
1. Singly Linked
List:
- Each node points to the next node in the
sequence.
- Efficient for forward traversal.
Head -> Node1 -> Node2 -> Node3
-> ... -> Tail -> null
2. Doubly Linked
List:
- Each node has references to both the next
and the previous nodes.
- Enables backward traversal.
Head <-> Node1 <-> Node2
<-> Node3 <-> ... <-> Tail <-> null
3. Circular Linked
List:
- The last node points back to the first
node, forming a closed loop.
Head -> Node1 -> Node2 -> Node3
-> ... -> Tail -> Head
Linked List Operations:
1. Insertion:
- Adding a new node to the list.
- Three scenarios:
- Insert at the beginning: Adjust the
"next" reference of the new node and update the head.
- Insert in the middle: Adjust the
"next" references of the surrounding nodes.
- Insert at the end: Update the
"next" reference of the current tail and set the new node as the new
tail.
2. Deletion:
- Nodes can be deleted from a linked list.
- Deleting the first node requires updating
the head.
- Deleting the last node involves updating
the reference of the second-to-last node.
- Deleting a node in the middle requires
adjusting the references of neighboring nodes.
3. Traversal:
Traversing a linked list involves visiting
each node in the sequence.
- This is typically done using a loop that
starts at the head and iterates through the nodes until the end is reached.
4. Search:
- Finding a specific value in the linked
list.
- Requires traversing the list until the
value is found or reaching the end (null).
5. Updation:-
- Finding a specific value in the linked
list.
- Requires traversing the list until the
value is found or reaching the end (null).
- Replace old value to new value.
=============================================================
Single link list
A singly linked
list is a special type of linked list in which each node has only one
link that points to the next node in the linked list.
Characteristics:
Each node holds a
single value and a reference to the next node in the list.
The list has a
head, which is a reference to the first node in the list, and a tail, which is
a reference to the last node in the list.
The nodes are not
stored in a contiguous block of memory, but instead, each node holds the
address of the next node in the list.
Accessing elements
in a singly linked list requires traversing the list from the head to the
desired node, as there is no direct access to a specific node in memory.
Application of
Singly Linked Lists:
Memory management: Singly
linked lists can be used to implement memory pools, in which memory is
allocated and deallocated as needed.
Database indexing: Singly linked
lists can be used to implement linked lists in databases, allowing for fast
insertion and deletion operations.
Representing
polynomials and sparse matrices: Singly linked lists can be used to
efficiently represent polynomials and sparse matrices, where most elements are
zero.
Operating systems: Singly
linked lists are used in operating systems for tasks such as scheduling
processes and managing system resources.
Advantages of
Singly Linked Lists:
Dynamic memory
allocation:
Singly linked lists allow for dynamic memory allocation, meaning that the size
of the list can change at runtime as elements are added or removed.
Cache
friendliness: Singly
linked lists can be cache-friendly as nodes can be stored in separate cache
lines, reducing cache misses and improving performance.
Space-efficient: Singly
linked lists are space-efficient, as they only need to store a reference to the
next node in each element, rather than a large block of contiguous memory.
Disadvantages of
Singly Linked Lists:
Poor random access
performance:
Accessing an element in a singly linked list requires traversing the list from
the head to the desired node, making it slow for random access operations
compared to arrays.
Increased memory
overhead: Singly
linked lists require additional memory for storing the pointers to the next
node in each element, resulting in increased memory overhead compared to
arrays.
Vulnerability to
data loss: Singly
linked lists are vulnerable to data loss if a node’s next pointer is lost or
corrupted, as there is no way to traverse the list and access other elements.
Not suitable for
parallel processing: Singly
linked lists are not suitable for parallel processing, as updating a node
requires exclusive access to its next pointer, which cannot be easily done in a
parallel environment.
Backward
traversing not possible: In singly linked list does not support backward
traversing.
Representation of
Single linked list:
A Node Creation:
Creating a node in
a linked list involves allocating memory for the new node and setting its data
and next pointer. Below is a simple algorithm in a language-agnostic pseudocode
to create a node in a singly linked list:
Algorithm:
CreateNode
Input: data (value to
be stored in the node)
Output: newNode (a
newly created node)
1. Allocate
memory for a new node (let's call it newNode).
2. Set the data of
newNode to the input data.
3. Set the next
pointer of newNode to NULL (as it is the last node in the beginning).
Return newNode.
Example :- Node creation in a linked list using C++ and
Python.
C++ Example:
#include
<iostream>
// Define the
structure for a node
struct Node {
int data;
Node* next;
};
// Function to
create a new node
Node*
createNode(int data) {
// Allocate memory for a new node
Node* newNode = new Node;
// Set the data of the new node
newNode->data = data;
// Set the next pointer to NULL
newNode->next = nullptr;
// Return the newly created node
return newNode;
}
int main() {
// Example usage
Node* myNode = createNode(42);
std::cout << "Node created with
data: " << myNode->data << std::endl;
// Don't forget to delete the allocated
memory when you're done using the node
delete myNode;
return 0;
}
Python Example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to
create a new node
def
create_node(data):
# Instantiate a new Node
new_node = Node(data)
# Return the newly created node
return new_node
# Example usage
my_node =
create_node(42)
print(f"Node
created with data: {my_node.data}")
# In Python,
memory management is handled by the garbage collector, so there's no need to
explicitly free memory
=================================================================
0 Comments