Overview of Linked List

 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

 =================================================================




Post a Comment

0 Comments