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.

 

 

Linked List in ds

 

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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);
}
#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); }
#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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
}
#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; } }
#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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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;
}
}
}
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; } } }
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

Share this post

One thought on “Linked list Data Structure

Leave a Reply

Your email address will not be published. Required fields are marked *