Page 106 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 7: Linked Lists

The primary disadvantages of doubly linked lists are: Notes
Each node requires an extra pointer, requiring more space.
The insertion or deletion of a node takes a bit longer (more pointer operations)
A generic doubly linked list node can be designed as:
typedef struct node {
void* data;
struct node* next;
struct node* prev;
} node;
node* head = (node*) malloc(sizeof(node));
The design of the node allows flexibility of storing any data type as the linked list data.

Example:
Head→ data = malloc(sizeof(int)); head→ data = 12;
or
head→ data = malloc(strlen(“guna”)+1);strcpy(head→ data, “guna”);
One operation that can be performed on doubly linked list is to delete a given node pointed by
‘p’. Function for this operation is given below:
delete(struct node *p)
{
if (p==Null) print f(“Node Not Found”)
else
{
p→llink →rlink=p→llink;
p→rlink→llink= p→llink;
free(p);
}
}

Task Analyse the applications of doubly linked lists.

7.2.3 Multilinked List

A multilinked list is a more general linked list with multiple links from nodes.
For examples, we can define a Node that has two references, age pointer and a name pointer.
With this structure it is possible to maintain a single list, where if we follow the name pointer
we can traverse the list in alphabetical order of names and if we traverse the age pointer, we can
traverse the list sorted by ages. This type of node organization may be useful for maintaining a
customer list in a bank where same list can be traversed in any order (name, age, or any other
criteria) based on the need.

LOVELY PROFESSIONAL UNIVERSITY 99