i) Insertion (all cases) - ii) Traversal (forward and backward) -

Marks: 10 M

Year: Dec 2013, May 2013, Dec 2012

1. Doubly linked list:

i. A doubly linked list is one in which all nodes are linked together by multiple links which help in accessing both the successor and predecessor node for any arbitrary node within the list.

ii. Every nodes in the doubly linked list has three fields: LeftPointer, RightPointer and DATA.

iii. The last node has a next link with value NULL, marking the end of the list, and the first node has a prev link with the value NULL. The start of the list is marked by the head pointer.

iv. Diagram:

Figure 1: Doubly linked list

2. Algorithm:

Assume that START is the first element in the linked list and TAIL is the last element of linked list.

i. Insert At Beginning

1. Start
2. Input the DATA to be inserted
3. Create a new node.

4. NewNode → Data = DATA NewNode →Lpoint =NULL

5. IF START IS NULL NewNode→ Rpoint = NULL

6. Else NewNode → Rpoint = START START→Lpoint = NewNode
7. START =NewNode
8. Stop

ii. Insertion at location:

1. Start
2. Input the DATA and POS
3. Initialize TEMP = START; i = 0
4. Repeat the step 4 if (i less than POS) and (TEMP is not equal to NULL)
5. TEMP = TEMP → RPoint; i = i +1
6. If (TEMP not equal to NULL) and (i equal to POS)

(a) Create a New Node

(b) NewNode → DATA = DATA

(c) NewNode → RPoint = TEMP → RPoint

(d) NewNode → LPoint = TEMP

(e) (TEMP → RPoint) → LPoint = NewNode

1. (f ) TEMP → RPoint = New Node

2. Else

(a) Display “Position NOT found”

1. Stop

iii. Insert at End

1. Start
2. Input DATA to be inserted
3. Create a NewNode
4. NewNode → DATA = DATA
5. NewNode → RPoint = NULL
6. If (SATRT equal to NULL)

a. START = NewNode

b. NewNode → LPoint=NULL

1. Else

a. TEMP = START

b. While (TEMP → Next not equal to NULL)

i. TEMP = TEMP → Next

c. TEMP → RPoint = NewNode

d. NewNode → LPoint = TEMP

1. Stop

iv. Forward Traversal

1. Start
2. If (START is equal to NULL)

a) Display “The list is Empty”

b) Stop

1. Initialize TEMP = START
2. Repeat the step 5 and 6 until (TEMP == NULL )
3. Display “TEMP → DATA”
4. TEMP = TEMP → Next
5. Stop

v. Backward Traversal

1. Start
2. If (START is equal to NULL)
3. Display “The list is Empty”
4. Stop
5. Initialize TEMP = TAIL
6. Repeat the step 5 and 6 until (TEMP == NULL )
7. Display “TEMP → DATA”
8. TEMP = TEMP → Prev
9. Stop