Scribd
Upload
102 views12 pages

Linked List Insertion Algorithms

This document discusses insertion in linked lists. It outlines algorithms for inserting a node at the beginning of a linked list, inserting after a given node, and inserting into a sorted linked list. The algorithms describe removing a node from the available list to use as the new node, updating the link fields to insert the new node in the correct position, and checking for overflow if no available nodes remain. Review questions ask about conditions for an empty list, inserting after a given node, and which pointer fields are changed in different insertion cases.

Uploaded by

Mandeep Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
102 views12 pages

Linked List Insertion Algorithms

This document discusses insertion in linked lists. It outlines algorithms for inserting a node at the beginning of a linked list, inserting after a given node, and inserting into a sorted linked list. The algorithms describe removing a node from the available list to use as the new node, updating the link fields to insert the new node in the correct position, and checking for overflow if no available nodes remain. Review questions ask about conditions for an empty list, inserting after a given node, and which pointer fields are changed in different insertion cases.

Uploaded by

Mandeep Kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Data Structures

Insertion in Linked List


Outlines
• Insertion Algorithm
– Insertion at the beginning
– Insertion after a given node
– Insertion into a sorted list
• Review Questions
Insertion into a Linked List

 New node N (which is to be inserted) will come from AVAIL


list.
• First node in the AVAIL list will be used for the new node N.

 Types of insertion:
• Insertion at the beginning
• Insertion between two nodes
Checking the Available List

AVAIL

ITEM Ø

Free-Storage List
NEW
Insertion at the beginning of Linked List

START

ITEM
Insertion Algorithm (Beginning of the list)

INSFIRST (INFO, LINK, START, AVAIL, ITEM)

1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and


Exit.
2. [Remove first node from AVAIL list]
Set NEW= AVAIL and AVAIL= LINK [AVAIL].
3. Set INFO [NEW] = ITEM. [Copy the new data to the node].
4. Set LINK [NEW] = START. [New node points to the original first
node].
5. Set START = NEW. [START points to the new node.]
6. EXIT.
Insertion after a given node
START

ITEM
Insertion Algorithm (After a given node)
INSLOC (INFO, LINK, START, AVAIL, LOC, ITEM)

1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and


Exit.
2. [Remove first node from AVAIL list]
Set NEW= AVAIL and AVAIL= LINK [AVAIL].
3. Set INFO [NEW] = ITEM. [Copy the new data to the node].
4. If LOC = NULL, then: [Insert as a first node]
Set LINK [NEW] = START and START = NEW.
Else: [Insert after node with location LOC.]
Set LINK [NEW] = LINK [LOC] and LINK [LOC] = NEW.
[End of If structure.]
5. Exit.
Insertion into a sorted Linked List
• If ITEM is to be inserted into a sorted linked list. Then ITEM must be
inserted between nodes A and B such that:
INFO [A] < ITEM < INFO [B]
• First of all find the location of Node A
• Then insert the node after Node A.

INSERT (INFO, LINK, START, AVAIL, ITEM)

1. CALL FIND_A (INFO, LINK, START, AVAIL, ITEM)


[USE Algorithm FIND_A to find the location of node preceding
ITEM.]
2. CALL INSLOC (INFO, LINK, START, AVAIL, LOC, ITEM)
[Insert ITEM after a given node with location LOC.]
3. Exit.
FIND_A (INFO, LINK, START, ITEM, LOC)

1. [List Empty?] If START = NULL, then: Set LOC = NULL, and


Return.
2. [Special Case?] If ITEM < INFO [START], then: Set LOC = NULL,
and Return.
3. Set SAVE = START and PTR = LINK [START]. [Initializes pointers]
4. Repeat step 5 and 6 while PTR ≠ NULL.
5. If ITEM < INFO [PTR] then:
Set LOC = SAVE, and Return.
[End of If Structure.]
6. Set SAVE = PTR and PTR = LINK [PTR]. [Update pointers]
[End of Step 4 Loop.]
7. Set LOC = SAVE.
8. Return.
Review Questions
• What is the condition for the list being empty?

• How will you insert a node in a linked list after a given


node?

• Which pointer fields are changed when:


– a node is inserted after a given node
– a node is inserted at the end of list
– a node is inserted at the beginning of the list.

You might also like