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

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