Deletion of a Node from Doubly Linked List

This article is part of article series - "Datastructures".

Previous Article: Inserting a Node in Doubly Linked List.

Deletion of a Node 

Let us say our current Doubly Linked List is as shown in Figure-1.

Figure 1: Current Doubly Linked List

• Deleting First Node of the List
Now we have to delete First Node from the List shown in Figure-1. Because of this operation HEAD and Node-2 are affected.

In HEAD - FIRST variable should now point to NODE-2 (i.e HEAD->FIRST = HEAD->FIRST->NEXT). If you see HEAD->FIRST->NEXT actually HEAD->FIRST currently points to NODE-1 so HEAD->FIRST->NEXT is equivalent to NODE-1->NEXT which is NODE-2.

In NODE-2 - NEXT variable remains unchanged and PREV variable should now point to NULL since it is the first Node in the List.

Decrement LENGTH variable in HEAD so that it maintains proper count of Nodes in the List.

Pseudocode:

HEAD->FIRST = HEAD->FIRST->NEXT

NODE-2->PREV = NULL

decrement(HEAD->LENGTH)

Output:

Figure 2: After deleting the First Node in the List.

Inserting a Node in Doubly Linked List

This article is part of article series - "Datastructures"

Previous Article: Doubly Linked List                                           Next Article: Deletion of a Node from Doubly Linked List.

Insertion of a Node

Before we discuss about how to insert a NODE let us discuss few rules to follow at the time of insertion.

• Check the location into which the user want to insert a new NODE. The possible locations where an user can insert a new node is in the range of 1 <= loc <= (length of list)+1. Let us say the length of the list is 10 & the user want to insert at location 12 (sounds stupid).


• As we know we can traverse Bi-Directional in case of Doubly Linked Lists so we have to take care of PREV and NEXT variables in the NODE structure. We should also update the neighboring Nodes which are affected by this operation. If not we might break up the List somewhere or the other by creating a BROKEN LIST.

We have following scenarios in the case of insertion of a NODE.

• Adding a Node at the start of the Empty List



Figure 1: Empty List and the newNode we want to add

As shown in Figure-1 we have a Empty List with LENGTH set to 0 and FIRST pointing to NULL. Let us add newNode at Location 1. 

In HEAD - FIRST variable points to newNode (head->FIRST = newNode).

In newNode - NEXT and  PREV points to NULL as we don't have any other Nodes in the List.

Increment the LENGTH variable in HEAD once insertion is successful to maintain the count of number of Nodes in the List.

Pseudocode:

HEAD->FIRST = newNode

newNode->PREV = NULL

newNode->NEXT = NULL

increment(HEAD->LENGTH)

Output:

Figure 2: After adding newNode in Empty List. (Changes in BLUE)

Implementation of Doubly Linked List in C

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called Nodes. Each Node contains two fields, called Links, that are references to the Previous and to the Next Node in the sequence of Nodes as well as field named Data.
For every Linked List we have something called Head which marks the starting of a list. So we have two main structures namely

• Node
• Head

Why we need a new structure for HEAD variable ? 
Just for convenience I decided to have HEAD its own structure. You can even use the Node structure.

Node
Every Node in a Doubly Linked List has three main members namely

• PREV
• DATA
• NEXT

As their names say

• PREV - holds the memory location of the Previous Node in the List. If there are none we point towards NULL. For the First Node in the List PREV points to NULL.
• NEXT - holds the memory location of the Next Node in the List. If there are none we point towards NULL. For the Last Node in the List NEXT points to NULL.
• DATA - In simple words it holds Data. In our case it holds the memory location to the actual data to be held by the Node.

typedef struct node
{
    struct node *prev;
    void        *data;
    struct node *next;
}NODE;

Head

Head acts as the  "head" of the List. Head structure has two members namely

• LENGTH - holds the count of number of Nodes in the List.
• FIRST - hold the memory location of the first Node in the List. If the List is EMPTY it points to NULL.

typedef struct head 
{
    unsigned int length;
    struct node  *first;
}HEAD;

NOTE: Our Head structure doesn't contain any pointer to the Tail of the List. Eventhough its a best way to include a pointer to Tail Node we decided to cover that implementation in Circular Doubly Linked List.

Notification Chains in Linux Kernel - Part 03

Continuation after PART-2.


Notifying Events on a Chain 
Notifications are generated with notifier_call_chain. This function simply invokes, in order of priority, all the callback routines registered against the chain. Note that callback routines are executed in the context of the process that calls notifier_call_chain. A callback routine could, however, be implemented so that it queues the notification somewhere and wakes up a process that will look at it.

NOTE: Similar to register and unregister functions we don't directly call notifier_call_chain function as we have wrapper functions for respective chains.

 <kernel/notifier.c>

 58 static int __kprobes notifier_call_chain(struct notifier_block **nl,
 59                     unsigned long val, void *v,
 60                     int nr_to_call, int *nr_calls)
 61 {
 62     int ret = NOTIFY_DONE;
 63     struct notifier_block *nb, *next_nb;
 64 
 65     nb = rcu_dereference(*nl);
 66 
 67     while (nb && nr_to_call) {
 68         next_nb = rcu_dereference(nb->next);
 69         ret = nb->notifier_call(nb, val, v);
 .
 76         nb = next_nb;
 77         nr_to_call--;
 78     }
 79     return ret;
 80 }

• nl
  Notification chain. 


• val
  Event type. The chain itself identifies a class of events; val unequivocally identifies an event type (i.e., NETDEV_REGISTER). 


• v
  Input parameter that can be used by the handlers registered by the various clients. This can be used in different ways under different circumstances. For instance, when a new network device is registered with the kernel, the associated notification uses v to identify the net_device data structure.


• nr_to_call
  Number of notifier functions to be called. Don't care value of this parameter is -1. 


• nr_calls
  Records the number of notifications sent. Don't care value of this field is NULL.

Notification Chains in Linux Kernel - Part 02

Continuation after PART-1.

Check the PART-3. 

Blocking Notifier chains
A blocking notifier chain runs in the process context. The calls in the notification list could be blocked as it runs in the process context. Notifications that are not highly time critical could use blocking notifier chains.

Linux modules use blocking notifier chains to inform the modules on a change in QOS value or the addition of a new device.

<kernel/notifier.c>

186 int blocking_notifier_chain_register(struct blocking_notifier_head *nh,
187         struct notifier_block *n)
188 {
.
199     down_write(&nh->rwsem);
200     ret = notifier_chain_register(&nh->head, n);
201     up_write(&nh->rwsem);
202     return ret;
203 }
204 EXPORT_SYMBOL_GPL(blocking_notifier_chain_register)
.
216 int blocking_notifier_chain_unregister(struct blocking_notifier_head *nh,
217         struct notifier_block *n)
218 {
.
229     down_write(&nh->rwsem);
230     ret = notifier_chain_unregister(&nh->head, n);
231     up_write(&nh->rwsem);
232     return ret;
233 }
234 EXPORT_SYMBOL_GPL(blocking_notifier_chain_unregister);