Sunday, September 25, 2022

Data Structure II (Link List 1)- Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations meaning they are not stored in locations like an array. The elements in a linked list are connected via pointers. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. In a doubly linked list, there is also a reference to the previous pointer of the list.
















Formally a link list is like:-


In a linear list implementation, there are always head and tail nodes, and inserting to them is a 

O(1) operation.

In Linked List implementation, it has the following characteristics:

1)Insertion - O(1)

2)Deletion - O(n)

3)Searching - O(n)

Therefore Insertion operation with O(1) stands out. Link List is being trivial data structure but has two key points:-

1) Insertion operation is O(1)

2) The list is dynamically resized.

In a singly link list there is a node and pointer to the next node.




This is a single link list.


Link List Structure:

struct node

{

    int info;

    struct node *next;

};

Types of Linked Lists:

  • Simple Linked List – In this type of linked list, one can move or traverse the linked list in only one direction
  • Doubly Linked List – In this type of linked list, one can move or traverse the linked list in both directions (Forward and Backward)
  • Circular Linked List – In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer and the first/head node contains the link of the last node of the linked list in its prev pointer



#include <stdio.h>
#include <stdlib.h>
  
struct Node {
    int data;
    struct Node* next;
};
  
// This function prints contents of linked list starting
// from the given node
void printList(struct Node* n)
{
    while (n != NULL) {
        printf(" %d ", n->data);
        n = n->next;
    }
}
  
// Driver's code
int main()
{
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;
  
    // allocate 3 nodes in the heap
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));
  
    head->data = 1; // assign data in first node
    head->next = second; // Link first node with second
  
    second->data = 2; // assign data to second node
    second->next = third;
  
    third->data = 3; // assign data to third node
    third->next = NULL;
  
    // Function call
    printList(head);
  
    return 0;
}

Linked List Applications

  • Dynamic memory allocation
  • Implemented in stack and queue
  • In undo functionality of softwares
  • Hash tables, Graphs

Linked List Complexity

Time Complexity

 Worst caseAverage Case
SearchO(n)O(n)
InsertO(1)O(1)
DeletionO(1)O(1)

Space Complexity: O(n)


Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds




No comments:

Post a Comment