Implementation of double linked list | Data Structures Lab Manual

Definition:

A variant of a linked list in which each item has a link to the previous item as well as the next. This allows easily accessing list items backward as well as forward and deleting any item in constant time.
Also known as two-way linked list, symmetrically linked list.
A doubly linked list is a linked list in which each node has three fields namely data field, forward link (Flink) and backward link (Blink). Flink points to the successor node in the list whereas Blink points to the predecessor node.

Advantages:

Deletion process is easier
Additional pointer for previous node is not nessary.
Backwarding and forwarding traverse are possible.

Disadvantages :

More Memory space is required since it has two pointers.

Alogrithm steps:

                    Step 1: Read the list operation.

Step 2: If operation is Create then process the following steps.

1. Create the new node and allocate memory for the new node.

2. Read the data in the new node.

3. Assign Flink and Blink as NULL.

4. Assign current as new.

Step 3: If operation is Insertion do the following steps.

i) Check insertion at beginning is true then

1. Create the new node and allocate memory for the new node

2. Read the data in the new node.

3. Move the current node to start position

4. Assign new->Blink =Null

5. Assign new->Flink=current

6. Now assign current->Blink=new

ii) Insertion at between nodes is true then

1. Create the new node and allocate memory for the new node

2. Read the data in the new node.

3. Move the current node required position

4. Assign new node’s Blink=current.

5. Assign new node’s Flink=current->Flink

6. Assign current node’s Flink =new

iii) Insertion at between nodes is true then

1. Create the new node and allocate memory for the new node.

2. Read the data in the new node.

3. Move the current node to end position.

4. Assign current node’s Flink =new.

5. Assign new’s Blink as current.

6. Assign new’s Flink as NULL.

7. Move end pointer to new node.

Step 4: If operation is deletion then do the following steps.

i). Check deletion at beginning is true then.

1. Move current pointer to start position.

2. Move the start pointer next node in the link.

3. Assign start’s Blink as NULL.

4. Reallocate current node from memory.

ii) Check deletion between two nodes is true

1. Move the current pointer to required position.

2. Assign current’s->Blink->Flink as current’s Flink.

3. Assign currents’s->Flink->Blink as current’s Blink.

4. Reallocate current from memory.

iii) Check deletion at end is true

1. Move the current pointer to end position.

2. Assign current’s->Blink->Flink as Null.

3. Reallocate current from memory.

4. Reallocate current from memory.

Step 5: If the operation is traversing.

i) Check deletion at end is true

1. Move the current pointer to end position.

2. Repeat the following steps until current becomes NULL.

3. Display the data.

4. Current=current->Flink.

ii) If Backward traversing then

1. Move the current to end position.

2. Repeat the following steps until current becomes NULL.

3. Display the data.

4. Current=current->Flink.

C Program To Implement Double linked list

CPP Program To Implement Double linked list

⇓Student Projects⇓

⇑Student Projects⇑