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:
-
Singly Linked List:
- Each node has a data field and a reference to the next node.
- The last node points to
nullto indicate the end of the list.
-
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.
-
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.
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)
#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();
}
}
#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;
}
#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;
}
Demonstration
Linked list Data Structure-DevsEnv