Algorithm


A linked list is a linear data structure in which elements are stored in nodes, and each node points to the next node in the sequence. Unlike arrays, linked lists do not have a fixed size, and their size can be dynamically changed during program execution. Each node in a linked list contains two fields: a data field to store the element and a reference (or link) field to point to the next node in the sequence.

There are several types of linked lists, including:

  1. Singly Linked List:

    • Each node has a data field and a reference to the next node.
    • The last node points to null to indicate the end of the list.

    Singly Linked List

  2. Doubly Linked List:

    • Each node has a data field, a reference to the next node, and a reference to the previous node.
    • Allows for traversal in both forward and backward directions.

    Doubly Linked List

  3. Circular Linked List:

    • Similar to a singly or doubly linked list, but the last node points back to the first node (or head) in the case of a circular singly linked list.

    Circular Linked List

Linked lists have several advantages and disadvantages:

Advantages:

  • Dynamic size: Linked lists can grow or shrink during runtime.
  • Easy to insert or delete elements in the middle of the list.

Disadvantages:

  • Random access is not efficient; you have to traverse the list from the beginning.
  • Extra memory is needed for the link fields.

 

Code Examples

#1 Linked List Implementations in Python

Code - Python Programming

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

# Example usage:
my_list = LinkedList()
my_list.append(1)
my_list.append(2)
my_list.append(3)
Copy The Code & Try With Live Editor

#2 Linked List Implementations in Java

Code - Java Programming

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    public LinkedList() {
        this.head = null;
    }

    // Method to insert a new node at the end of the linked list
    public void append(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
            return;
        }

        Node last = head;
        while (last.next != null) {
            last = last.next;
        }

        last.next = newNode;
    }

    // Method to display the linked list
    public void display() {
        Node current = head;

        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }

        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();

        // Appending elements to the linked list
        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.append(4);

        // Displaying the linked list
        System.out.println("Linked List: ");
        linkedList.display();
    }
}
Copy The Code & Try With Live Editor

#3 Linked List Implementations in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

// Define a node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a new node at the beginning of the list
void insertAtBeginning(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// Function to insert a new node at the end of the list
void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

// Function to print the elements of the linked list
void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Function to free the memory allocated for the linked list
void freeList(struct Node* head) {
    struct Node* current = head;
    struct Node* next;
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    struct Node* head = NULL;

    // Insert some elements at the beginning
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);

    // Insert some elements at the end
    insertAtEnd(&head, 4);
    insertAtEnd(&head, 5);

    // Print the linked list
    printf("Linked List: ");
    printList(head);

    // Free the memory
    freeList(head);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Linked List Implementations in C++

Code - C++ Programming

#include <iostream>

// Node class to represent each element in the linked list
template  < typename T>
class Node {
public:
    T data;
    Node* next;

    Node(T value) : data(value), next(nullptr) {}
};

// LinkedList class to manage the linked list operations
template  < typename T>
class LinkedList {
private:
    Node* head;

public:
    LinkedList() : head(nullptr) {}

    // Insert a new node at the end of the list
    void append(T value) {
        Node* newNode = new Node(value);

        if (!head) {
            head = newNode;
        } else {
            Node < T>* current = head;
            while (current->next) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    // Display the elements of the linked list
    void display() {
        Node < T>* current = head;
        while (current) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }

    // Destructor to free the memory allocated for nodes
    ~LinkedList() {
        Node < T>* current = head;
        Node* nextNode;

        while (current) {
            nextNode = current->next;
            delete current;
            current = nextNode;
        }
        head = nullptr;
    }
};

int main() {
    LinkedList < int> linkedList;

    // Append elements to the linked list
    linkedList.append(1);
    linkedList.append(2);
    linkedList.append(3);

    // Display the linked list
    linkedList.display();

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Linked list Data Structure-DevsEnv