Doubly Linked Lists Carnegie Mellon School of （双链表的卡内基梅隆大学上学）.pdf

Lecture 11 Doubly Linked Lists Array of Linked Lists In this lecture • Doubly linked lists • Array of Linked Lists • Creating an Array of Linked Lists • Representing a Sparse Matrix • Defining a Node for a Sparse Matrix • Exercises • Solutions Doubly Linked Lists A doubly linked list is a list that contains links to next and previous nodes. Unlike singly linked lists where traversal is only one way, doubly linked lists allow traversals in both ways. 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. For example, head data = malloc(sizeof(int)); *((int*)(head data)) = 12; or head data = malloc(strlen(“guna”)+1); strcpy((char*)(headdata), “guna”); Copyright @ 2009 Ananda Gunawardena Inserting to a Doubly Linked Lists Suppose a new node, newnode needs to be inserted after the node current current newnode The following code can then be written newnode next = currentnext; currentnext = newnode; newnodeprev = current; (newnodenext)prev = newnode; Deleting a Node from a Doubly Linked Lists Suppose a new node, current needs to be deleted current The following code can then be written node* N = currentprev N next = currentnext; (Nnext)prev = N; free(current);