LINKED LIST
Linked List is collection of objects stored in list form
Linked List is sequence of items (objects) where every item is linked to next
Non-Primitive data structure in which each element is dynamically allocated & in
which elements point to each other to define linear relationship
Operations on Linked List Applications of Linked List
Insert Representation of polynomial
Insert at First Position Graph Representation
Insert at Last Position Symbolic Expressions
Insert into ordered List Dynamic Hashing
Delete Implementation of stack & queue
Traverse List
Copy Linked List
Types of Linked List
1. Singly Linked List
Basic Type of linked list
Each node contains data & pointer to next node
Last node’s pointer is null
Advantages : Less Memory
Disadvantages : Traverse only in one direction i.e forward
2. Circular Linked List
It is singly linked list where last node points to first node in list
All nodes are connected to form circle
No null pointer at end
Advantage : Time Saving & Efficient Insertion & Deletion
Disadvantage : Traversal Complexity & more memory utilisation
3. `Doubly Linked List
Each node contains data & 2 pointers : LPTR(left pointer) & RPTR (right pointer)
LPTR points previous node while RPTR points next node
Advantages : Delete node easily
Disadvantages : Requires more memory
Advantages of Linked List over Array Disadvantages of Linked List over Array
1. Dynamic Structures 1. Binary Search cant be implemented
2. Efficient Memory Utilisation 2. Cannot be easily sorted
3. Insertion & Deletion are easier & efficient 3. More complex to create
4. Elements of Linked List are flexible 4. More memory
Advantages of Doubly Linked List over Singly Linked List
1. Easy Deletion
2. Traverse in both direction
3. 2 pointer so more flexible
4. More Efficient
SINGLY LINKED LIST
Insertion at First Position Insertion at End Position
Function : INSERT (X, FIRST) Function : INSEND(X, FIRST)
X = New Element {First 3 steps same }
FIRST = pointer of first element
4. [Initialize field of new node]
AVAIL = pointer to top of availability stack
INFO (NEW) ← X
NEW = temporary pointer variable
Node contains INFO & LINK fields LINK (NEW) ← NULL
1. [Underflow] 5. [Is first empty?]
If AVAIL = NULL If FIRST = NULL
then write (‘Availability Stack then Return (NEW)
Underflow’ 6. [Initialize search for last node]
Return (FIRST) SAVE ← FIRST
2. [Obtain address of next free node] 7. [Search at end of list]
NEW ← AVAIL
Repeat while LINK (SAVE) ≠ NULL
3. [Remove free node from availability stack]
AVAIL ← LINK (AVAIL) SAVE ← LINK (SAVE)
4. [Initialize fields of new node & its link to list] 8. [Set link field of last node to NEW]
INFO (NEW) ← X LINK (SAVE) ← NEW
LINK (NEW) ← FIRST 9. [Return first node pointer]
5. [Return address of new node] Return (FIRST)
Return (NEW)
Insertion in Sorted List (Ordered) Deletion
Function : INSORD (X, FIRST) Function : DELETE (X, FIRST)
NEW, SAVE = Temporary pointer variable X = address of node which we want to delete
Function inserts new node such that linked list FIRST = pointer to first element of linked linear list
preserves ordering of terms in increasing SAVE, PRED = Temporary Pointer Variable
order of their INFO field 1. [Is empty list?]
{first 3 steps same} If FIRST = NULL
1. [Is list empty] then write (‘Underflow’)
If FIRST = NULL Return
then LINK (NEW) ← NULL 2. [Initialize search for X]
Return (NEW) SAVE ← FIRST
2.[Does new node precede all other node in 3. [Find X]
list] Repeat through Step – 5
If INFO (NEW) < INFO (FIRST) while SAVE ≠ X and LINK (SAVE) ≠ NULL
then LINK (NEW) ← FIRST 4. [Update predecessor maker]
Return (NEW) PRED ← SAVE
3. [Initialize temporary pointer] 5. [Move to next node]
SAVE ← FIRST SAVE ← LINK (SAVE)
4. [Search for predecessor of new node] 6. [End of List]
Repeat while LINK (SAVE) ≠ NULL If SAVE ≠ X
and INFO (NEW) > INFO (LINK (SAVE)) then write (‘Node not found’)
SAVE ← LINK (SAVE) return
5. [Set link field of new node & its 7. [Delete X]
predecessor] If X = FIRST
LINK (NEW) ← LINK (SAVE) then FIRST ← LINK (FIRST)
LINK (SAVE) ← NEW else LINK (PRED) ← LINK (X)
6. [Return first node pointer] 8. [Free Deleted Node]
Return (FIRST) Free (X)
COPY (FIRST)
5. [Update predecessor & save pointer]
1. [Is Empty List?] PRED ← NEW
If FIRST = NULL SAVE ← LINK (NEW)
then return (NULL)
6. [Copy node]
2. [Copy first node] If AVAIL = NULL
NEW ← NODE then write (‘Availability stack underflow’)
NEW ← AVAIL Return (0)
AVAIL ← LINK (AVAIL) else NEW ← AVAIL
FIELD (NEW) ← INFO (FIRST) AVAIL ← LINK (AVAIL)
BEGIN ← NEW FIELD (NEW) ← INFO (SAVE)
3. [Initialize traversal] PTR (PRED) ← NEW
SAVE ← FIRST 7. [Set link of last node & return]
4. [Move next node if not at end of list] PTR (NEW) ← NULL
Repeat thru step 6 while (SAVE) ≠ NULL Return (BEGIN)
Circular Linked List Algorithm
Insertion at First Position Insertion at End Position
FUNCTION : CIRCULAR_LINK_INSERT_FIRST FUNCTION : CIRCULAR_LINK_INSERT_END
(X, FIRST, LAST) (X, FIRST, LAST)
1. [Create New Empty Node] 1. [Create New Empty Node]
NEW ← NODE NEW ← NODE
2. [Initialise fields of new node & its link to list] 2. [Initialise fields of new node and its link
INFO (NEW) ← X to list]
If FIRST = NULL If FIRST = NULL
then LINK(NEW) ← NEW then LINK(NEW) ← NEW
FIRST ← LAST ← NEW FIRST ← LAST ← NEW
else LINK(NEW) ← FIRST else LINK(NEW) ← FIRST
LINK (LAST) ← NEW LINK (LAST) ← NEW
FIRST ← NEW FIRST ← NEW
return return
DOUBLY LINKED LIST ALGORITHM
Insertion : FUNCTION : DOUBINS (L, R, M, X)
1. [Create new empty node]
NEW ← NODE Deletion
FUNCTION : DOUBDEL (L,R, OLD)
2. [Copy information field]
INFO (NEW) ← X 1. [Is underflow?]
If R = NULL
3. [Insert into empty field]
then write (‘Underflow’)
If R = NULL
return
then LPTR(NEW) ← RPTR (NULL) ← NULL
L ← R ← NEW 2. [Delete node]
Return If L = R
then L ← R ← NULL
4. [Is left most insertion]
else if OLD = L
If M = L
then L ←RPTR(L)
then LPTR(NEW) ← NULL
LPTR(L) ← NULL
RPTR (NEW) ← M
else if OLD = R
LPTR (M) ← NEW
L ← NEW then R ←LPTR(R)
RPTR(R) ← NULL
Return
else RPTR(LPTR(OLD)) ←RPTR(OLD)
5. [Insert in middle] LPTR (RPTR(OLD)) ←LPTR(OLD)
LPTR (NEW) ← LPTR (M)
RPTR (NEW) ← M
3. [Free deleted node]
FREE (OLD)
LPTR (M) ← NEW
RPTR (LPTR(NEW)) ← NEW
