Page 101 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes great advantage, the overhead with storing and retrieving data can make a big difference.
Sometimes linked lists are hard to manipulate. If the last item is deleted, the last but one must
now have its pointer changed to hold a NULL reference. This requires that the list is traversed to
find the last but one link, and its pointer set to a NULL reference Finally, linked lists wastes
memory in terms of extra reference points.

7.1.1 Designing the Node of a Linked List

Linked list is a collection of linked nodes. A node is a struct with at least a data field and a
reference to a node of the same type. A node is called a self-referential object, since it contains a
pointer to a variable that refers to a variable of the same type.

Example: A struct Node that contains an int data field and a pointer to another node can
be defined as follows.
typedef struct node {
int data;
struct node* next;
} node;
node* head = NULL;

7.1.2 Creating the First Node

Memory must be allocated for one node and assigned to head as follows.
head = (node*) malloc(sizeof(node));
head→data = 10;
head→next = NULL;

Figure 7.2: Creating the First Node

head

10

Source: http://www.cs.cmu.edu/~ab/15-123S09/lectures/Lecture%2010%20-%20%20Linked%20List%
20Operations.pdf
7.1.3 Adding the Second Node and Linking

The second node is added in the following way:
node* nextnode = malloc(sizeof(node));
nextnodeàdata = 12;
nextnodeànext = NULL;
headànext = nextnode;

94 LOVELY PROFESSIONAL UNIVERSITY