DSA 3 DAYS Part 3

-

1. Introduction

A linked list is a data structure in which each item is connected to the next item through a link or reference. Each node in the linked list contains two parts:

  • Data: The value or data stored in the node.

  • Link: The reference to the next node in the sequence.

This structure forms a chain of nodes, allowing dynamic memory allocation and efficient insertions or deletions. Linked lists are fundamental in implementing more complex data structures like trees and graphs.

2. Representation

A linked list can be represented as a sequence of nodes, where each node points to the next. For example:

[Data | Link] -> [Data | Link] -> [Data | Link] -> NULL

3. Applications of Linked Lists

Linked lists are widely used in computer science for various purposes, including:

  1. Implementing Stacks and Queues: Efficiently manage dynamic sizes.

  2. Graphs: Used in the adjacency list representation of graphs.

  3. Hash Tables: Handle collisions using chaining.

  4. Polynomial Representation: Represent polynomials by storing coefficients and exponents in nodes.

4. Arrays vs. Linked Lists

Arrays

  • Fixed size determined at creation.

  • Easy access to any element using the index in constant time.

  • No space overhead.

  • Memory usage: n x sizeof(element).

Linked Lists

  • Dynamic size; grows or shrinks as needed.

  • Requires extra memory for storing links or references.

  • Memory usage: n x sizeof(element) + n x sizeof(reference).

  • No direct access to elements; traversal required.

5. Types of Linked Lists

  1. Singly Linked List: Each node has one link pointing to the next node.

  2. Doubly Linked List: Each node has two links, one to the next node and one to the previous node.

  3. Circular Linked List: The last node links back to the first node, forming a circular structure.

6. Operations on Linked Lists

Traversal

  1. Set PTR = Start.

  2. Repeat steps 3 and 4 while PTR != NULL:

    • Write info[PTR].

    • Set PTR = Link[PTR].

  3. Exit.

Searching in an Unsorted Linked List

  1. Set PTR = Start.

  2. Repeat while PTR != NULL:

    • If ITEM == info[PTR], set LOC = PTR and exit.

    • Else, set PTR = Link[PTR].

  3. If the search is unsuccessful, set LOC = NULL.

  4. Exit.

Insertion in a Linked List

At the Beginning

  1. Start.

  2. Create a new node.

  3. Set NewNode.Data = Data.

  4. Set NewNode.Link = Head.

  5. Update Head = NewNode.

  6. Exit.

At a Specific Position

  1. Start.

  2. Create a new node.

  3. Traverse the list to find the position (one node before the target position).

  4. Set NewNode.Data = Data.

  5. Set NewNode.Link = CurrentNode.Link.

  6. Update CurrentNode.Link = NewNode.

  7. Exit.

At the End

  1. Start.

  2. Create a new node.

  3. Traverse the list to find the last node.

  4. Set NewNode.Data = Data.

  5. Set NewNode.Link = NULL.

  6. Update the last node's link to NewNode.

  7. Exit.

Deletion in a Linked List

At the Beginning

  1. Start.

  2. Set PTR = Head.

  3. Update Head = Head.Link.

  4. Remove PTR.

  5. Exit.

At a Specific Position

  1. Start.

  2. Traverse the list to find the node before the target node.

  3. Update PTR.Link to skip the target node.

  4. Remove the target node.

  5. Exit.

At the End

  1. Start.

  2. Traverse the list to find the second-to-last node.

  3. Update SecondLastNode.Link = NULL.

  4. Remove the last node.

  5. Exit.

7. Stack

A stack is a linear data structure where all operations occur at one end, called the top. It follows the Last In, First Out (LIFO) principle.

Basic Operations

  1. Push: Add an element to the top.

  2. Pop: Remove the top element.

  3. Peek: View the top element without removing it.

  4. isFull: Check if the stack is full.

  5. isEmpty: Check if the stack is empty.

8. Queue

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Insertions occur at the rear, and deletions occur at the front.

Operations

  1. Enqueue: Add an element to the rear.

  2. Dequeue: Remove an element from the front.

  3. Peek: View the front element without removing it.

  4. Initialize: Set up the queue.

  5. isFull: Check if the queue is full.

  6. isEmpty: Check if the queue is empty.

Comments

Post a Comment

Popular posts from this blog

Keyword , Identifier, Indentation, Comments & Documentation

-
Keyword : In Python, a  keyword  is a special word that has a specific meaning and purpose in the language. These words are reserved, which means you can’t use them for anything other than their intended purpose. For example, you can’t use a keyword as a variable name. Here are a few examples of Python keywords and what they do: if : Used to make a decision. For example,  if x > 0: . for : Used to create a loop. For example,  for i in range(10): . def : Used to define a function. For example,  def my_function(): . True  and  False : Represent boolean values.  I dentifier : In Python, an  identifier  is simply a name you give to things like variables, functions, classes, or modules. It’s like a label that helps you refer to these elements in your code. Here are some key points about identifiers: Must start with a letter or an underscore (_) : For example,  name ,  _value . Cannot start with a number : For example,  1name...
Read more

DSA Lab 8 program

-
 Program for implementing multiple stack. # include < stdio.h > # include < stdlib.h > struct stack {     int maxstack;     int * stack;     int top; }; int isEmpty ( struct stack * ptr ) {     if ( ptr -> top == - 1 ) {         return 1 ;     } else {         return 0 ;     } } int isFull ( struct stack * ptr ) {     if ( ptr -> top == ptr -> maxstack - 1 ) {         return 1 ;     } else {         return 0 ;     } } int peek ( struct stack * ptr ) {     return ptr -> stack [ ptr -> top ]; } int pop ( struct stack * ptr ) {     if ( isEmpty (ptr) ) {         printf ( " Stack Underflow! Cannot pop from the stack \n " ) ;         return - 1 ;     } else {         in...
Read more

DSA Lab 7 Program

-
 Program for implementing Stack using array # include < stdio.h > int maxstack = 10 ; int stack [ 10 ]; int top = - 1 ; int empty (){     if (top == - 1 ){         return 1 ;     }     else {         return 0 ;     } } int full (){     if (top == maxstack){         return 1 ;     }     else {         return 0 ;     } } int peek (){     return stack [top]; } int pop (){     int data;     if ( ! empty () ){         data = stack [top];         top -= 1 ;         printf ( " The data has been Deleted. Your data is %d \n " , data) ;         return data;     }     else {         printf ( " The data Can't be Deleted. Becouse stack is empty \n " ) ;   ...
Read more