2_DSA-Linked List(PART-1)

Linked List
Linear data structure

Linked List
• A linked list is a linear data structure consisting
of a group of nodes where each node point to
the next node through a pointer.
Linked List
• Each node is composed of data and a reference
(in other words, a link) to the next node in the
sequence.
• In LL the elements are not stored at contiguous
memory locations. The elements are linked
using pointers.
• Linked list is a data structure which in turn can
be used to implement other data structures
such as stacks, queues, and their variations.
Linked List
Linked List
ARRAY VS LINKED LIST
Array vs Linked List
Arrays Linked List
• Elements are stored at • Elements are not
contiguous memory stored at a contiguous
locations. location; elements are
linked using pointers.
• The size of array is fixed. • Size is not fixed.
• Insertion/Deletion is • Ease of insertion and
costly. deletion.
• Random access is • Random access is not
allowed. allowed.
Types of Linked List
• Singly Linked List

• Doubly Linked List
• Circular Linked List
Singly Linked List (SLL)
• In this type of linked list, one can move or
traverse the linked list in only one
direction.
• In a SLL, we have a single pointer that will
point to the next node and, therefore, it is
called a singly linked list.
Construction of a Linked List
• Example: Create a linked list of 3 nodes
Data Address Data Address
Data Address
• Construct 3 nodes
• Allocate memory to them
• Connect nodes one by one with each
other.
• Example: Create the structure of a node
struct Node
{
int data; data next
struct Node* next;
};
• Example: Construct 3 nodes of same type:
struct Node
{
int data; data next
struct Node* next;
};
• struct Node* first= NULL;

• struct Node* second = NULL;
• struct Node* third = NULL;
• Example: Allocate memory to them
first = (struct Node*) malloc (sizeof(struct Node));
//Assume first = 1000
second = (struct Node*) malloc (sizeof(struct Node));
//Assume second = 2000
third = (struct Node*)malloc(sizeof(struct Node));
//Assume third = 3000
data next data next data next
1000 2000 3000

• Example: Assign the values:
• first->data = 1 first->next = second;
1 2000
• second->data = 2 second- >next = third;
1 2000 2 3000
• third->data = 3 third->next = NULL;

1 2000 2 3000 3 NULL
• Example: Assign the values:
• struct Node* start = first ;
1000 start
1 2000 2 3000 3 NULL
1000 2000 3000

first second third
#include <stdio.h> #include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
int main()
{
struct Node* start= NULL; struct Node* second = NULL; struct Node* third = NULL;
struct Node* first = NULL;
first = (struct Node*) malloc (sizeof(struct Node));
second = (struct Node*) malloc (sizeof(struct Node));
third = (struct Node*) malloc (sizeof(struct Node));
start = first;
first->data = 1; // assign data in first node
first->next = second; // Link first node with
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
return 0; }
Self Referential Structure
• struct Node
•{
int next;
struct Node next;
}
• Self Referential Structure is a structure which contains a
pointer that points to a variable of the same structure
type.
• Example: Linked list node.
• In a linked list, every node contains a pointer to another
node which is of the same type, it is also called a self-
Memory allocation and De-allocation for
a linked list.
Linked list creation
Linked list creation
Linked List Traversal
• Traversing a linked list means accessing the
nodes of the list in order to perform some
processing on them.
• Traversal and Searching
• START: pointer variable START which stores
the address of the first node of the list.
• End of the list is marked by storing NULL or
–1 in the NEXT field of the last node.
Linked List Traversal
Write an algorithm to print the number of nodes in
the list
Write an algorithm to search a value in the list
Searching means finding whether a given value is present
in the information part of the node or not
Write an algorithm to search a value in the list
Linked List: Insertion
• Insertion: Adding a new node into an already
existing linked list.
• Case 1: The new node is inserted at the
beginning.
• Case 2: The new node is inserted at the end.
• Case 3: The new node is inserted after a given
node.
• Case 4: The new node is inserted before a given
node.
Insertion at the beginning
Algorithm to insert a new node at
the end
Algorithm to insert a new node
after a node that has value NUM
Algorithm to insert a new node
before a node that has value NUM
Deleting a Node from a Linked List
• Case 1: The first node is deleted.
• Case 2: The last node is deleted.
• Case 3: The node after a given node is
deleted
Algorithm to delete the first node
Algorithm to delete the last node
Algorithm to delete the node after
a given node
Circular Linked List
End of the list?

The node that contains the address of the first
node is actually the last node of the list.
Circular LL: Insertion at
Beginning
Circular LL: Insertion at End
Circular LL: Deletion from Beg
Circular LL: Deletion from End
Doubly Linked List
Circular Doubly Linked List
Header Linked List
• A header linked list is a special type of
linked list which contains a header node at
the beginning of the list.
• Grounded header linked list: which stores
NULL in the next field of the last node.
• Circular header linked list: which stores the
address of the header node in the next
field of the last node.
Drawbacks of Linked List
• Random access is not allowed. We have to
access elements sequentially starting from
the first node(head node).
• Extra memory space for a pointer is
required with each element of the list.
• Not cache friendly. Since array elements
are contiguous locations, there is locality
of reference which is not there in case of
linked lists.
CAN WE DO BINARY SEARCH
USING LINKED LIST?

2_DSA-Linked List(PART-1)

Uploaded by

Copyright:

Available Formats

2_DSA-Linked List(PART-1)

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

2_DSA-Linked List(PART-1)

Uploaded by

Copyright:

Available Formats

Linked List

Linear data structure

• Singly Linked List

• struct Node* first= NULL;

data next data next data next

1000 2000 3000

• second->data = 2 second- >next = third;

• third->data = 3 third->next = NULL;

1 2000 2 3000 3 NULL

1000 2000 3000

End of the list?

You might also like