Linked list Data Structure
Linked list Data Structure
The linked list data structure ia a collection of nodes and each node is having one data field and next link field.
Any element can be accessed by sequential acess only. The structure does not necessarily reflect the logical organisation.Ithems may appear in any order. The logical oeganization is provided through pointers, Each item in the list is called as node that consists of a data portion containing the item information and pointer which contain location of the next item in the logical sequence which is to be maintained.
Types of Linked List
There are three types of linked list
-
- Simple Linked List
- Doubly Linked List
- Circular Linked List
Linked List Implementations in C
#include <stdio.h> #include <stdlib.h> // Creating a node struct node { int value; struct node *next; }; // print the linked list value void printLinkedlist(struct node *p) { while (p != NULL) { printf("%d ", p->value); p = p->next; } } int main() { // Initialize nodes struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist(head); }
Linked List Implementations in CPP
#include <bits/stdc++.h> #include <iostream> using namespace std; // Creating a node class Node { public: int value; Node* next; }; int main() { Node* head; Node* one = NULL; Node* two = NULL; Node* three = NULL; one = new Node(); two = new Node(); three = new Node(); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; head = one; while (head != NULL) { cout << head->value; head = head->next; } }
Linked List Implementations in Python
class Node: # Creating a node def __init__(self, item): self.item = item self.next = None class LinkedList: def __init__(self): self.head = None if __name__ == '__main__': linked_list = LinkedList() # Assign item values linked_list.head = Node(1) second = Node(2) third = Node(3) # Connect nodes linked_list.head.next = second second.next = third # Print linked list item while linked_list.head != None: print(linked_list.head.item, end=" ") linked_list.head = linked_list.head.next
Linked List Implementations in Java
class LinkedList { // Creating a node Node head; static class Node { int value; Node next; Node(int d) { value = d; next = null; } } public static void main(String[] args) { LinkedList linkedList = new LinkedList(); // Assign value values linkedList.head = new Node(1); Node second = new Node(2); Node third = new Node(3); // Connect nodess linkedList.head.next = second; second.next = third; // printing node-value while (linkedList.head != null) { System.out.print(linkedList.head.value + " "); linkedList.head = linkedList.head.next; } } }
Linked List Complexity
Time Complexity
Worst case | Average Case | |
---|---|---|
Search | O(n) | O(n) |
Insert | O(1) | O(1) |
Deletion | O(1) | O(1) |
Space Complexity: 0(n)
Linked List Applications
- Dynamic memory allocation
- Stack and queue
- Hash tables
- Graphs
Advantage of Linked List
- The node can be dynamically created. Hence there is no wastage of memory or lack of memory. The desored number of nodes can be created for the linked list
- The nodes can be physically deleted. That means the memory occupied by these node can be freed.
Disdvantage of Linked List
For a singly linked list, if we want to aceess some intermediate node then we have to traverse sequentially from the head node. Thus searching for the desired node is not efficient.
Read more, Deque Data Structure
Pingback: docker not allowing me to connect to 443 - Study Experts