written 8.0 years ago by | • modified 8.0 years ago |

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

**Marks:** 10 M

**Year:** Dec 2013, May 2013, Dec 2012

**1 Answer**

0

58kviews

What is doubly linked list? Write an algorithm to implement

written 8.0 years ago by | • modified 8.0 years ago |

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

**Marks:** 10 M

**Year:** Dec 2013, May 2013, Dec 2012

ADD COMMENT
EDIT

2

3.4kviews

written 8.0 years ago by |

**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

- Start
- Input the DATA to be inserted
- Create a new node.
NewNode → Data = DATA NewNode →Lpoint =NULL

IF START IS NULL NewNode→ Rpoint = NULL

- Else NewNode → Rpoint = START START→Lpoint = NewNode
- START =NewNode
- Stop

**ii. Insertion at location:**

- Start
- Input the DATA and POS
- Initialize TEMP = START; i = 0
- Repeat the step 4 if (i less than POS) and (TEMP is not equal to NULL)
- TEMP = TEMP → RPoint; i = i +1
- 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

(f ) TEMP → RPoint = New Node

Else

(a) Display “Position NOT found”

- Stop

**iii. Insert at End**

- Start
- Input DATA to be inserted
- Create a NewNode
- NewNode → DATA = DATA
- NewNode → RPoint = NULL
- If (SATRT equal to NULL)

a. START = NewNode

b. NewNode → LPoint=NULL

- Else

a. TEMP = START

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

i. TEMP = TEMP → Next

c. TEMP → RPoint = NewNode

d. NewNode → LPoint = TEMP

- Stop

iv. Forward Traversal

- Start
- If (START is equal to NULL)

a) Display “The list is Empty”

b) Stop

- Initialize TEMP = START
- Repeat the step 5 and 6 until (TEMP == NULL )
- Display “TEMP → DATA”
- TEMP = TEMP → Next
- Stop

v. Backward Traversal

- Start
- If (START is equal to NULL)
- Display “The list is Empty”
- Stop
- Initialize TEMP = TAIL
- Repeat the step 5 and 6 until (TEMP == NULL )
- Display “TEMP → DATA”
- TEMP = TEMP → Prev
- Stop

ADD COMMENT
EDIT

Please log in to add an answer.