Single Linked List
This lab teaches you the following topics:
- Creation of singly linked list
- Insertion in singly linked list
- Deletion from singly linked list
- Traversal of all nodes
Introduction
A list is a finite ordered set of elements of a certain type.
The elements of the list are called cells or nodes.
A list can be represented statically, using arrays or, more often, dynamically, by allocating and releasing memory as needed. In the case of static lists, the ordering is given implicitly by the one-dimension array. In the case of dynamic lists, the order of nodes is set by pointers. In this case, the cells are allocated dynamically in the heap of the program. Dynamic lists are typically called linked lists, and they can be singly- or doubly-linked.
A singly-linked list may be depicted as in Figure 1.1.
Lab Activities:
Activity 1:
Creation of linked list
Solution:
Consider the following steps which apply to dynamic lists:
- Initially, the list is empty. This can be coded by setting the pointers to the first and last cells to the special value
NULL, i.e. first = NULL, last = NULL.
- Reserve space for a new node to be inserted in the list:
/* reserve space */
p = ( NodeT * ) malloc( sizeof( NodeT ) ) ;
Then place the data into the node addressed by p. The implementation depends on the type of data the node holds. For primitive types, you can use an assignment such as ∗p = data.
- Make the necessary connections:
p−>next = NULL; /* node i s appended to the l i s t */
i f ( last != NULL ) /* l i s t i s not empty */
last−>next = p;
else
f i r s t = p; /* f i r s t node */
last = p;
Activity 2:
Accessing nodes of linked list
Solution:
The nodes of a list may be accessed sequentially, gathering useful information as needed. Typically, a part of the information held at a node is used as a key for finding the desired information. The list is scanned linearly, and the node may or may not be present on the list. A function for searching a specific key may contain the following sequence of statements:
NodeT *p;
p = f i r s t ;
while ( p != NULL )
i f ( p−>key = givenKey )
{
return p; /* key found at address p */
}
else
{
p = p−>next ;
return NULL; /* not found */
}
Activity 3:
Insertion in single linked list
Solution:
The node to be inserted may be created as shown at fig1.3. We will assume here that the node to insert is pointed to by p.
- If the list was empty then there would be only one node, i.e.
i f ( f i r s t == NULL )
{
f i r s t = p;
last = p;
p−>next = NULL;
}
- If the list was not empty, then insertion follows different patterns depending on the position where the node is to be Thus, we have the following cases:
- Insertion before the first node of the list:
i f ( f i r s t != NULL )
{
p−>next = f i r s t ;
f i r s t = p;
}
-
- Insertion after the last node of the list (this operation is also called append):
i f ( last != NULL )
{
p−>next= NUL L;
last−>next= p;
last= p;
}
- Insertion before a node given by its key.
There are two steps to execute:
a. Search for the node containing the given Key:
NodeT *q, *q1;
q1 = NULL; /* initialize */
q = f i r s t ;
while ( q != NULL )
{
i f ( q−>key == givenKey )
break;
q1 = q;
q = q−>next ;
}
b. Insert the node pointed to by p, and adjust links:
i f ( q != NULL )
{
/* node with key given Key has address q */
i f ( q == f i r s t )
{
/* insert after first node */
p−>next = f i r s t ;
f i r s t = p;
}
else
{
q1−>next = p;
p−>next = q;
}
}
- Insertion after a node given by its key. Again, there are two steps to execute:
a. Search for the node containing the givenKey:
NodeT *q, *q1;
q1 = NULL; /* initialize */
q = f i r s t ;
while ( q != NULL )
{
i f ( q−>key == givenKey ) break;
q1 = q;
q = q−>next ;
}
b. Insert the node pointed to by p, and adjust links:
i f ( q != NULL )
{
p−>next = q−>next ; /* node with key givenKey has address q */
q−>next = p;
i f ( q == last )
last = p;
}
Activity 4:
Deleting a node from single linked list
Solution:
When we are to remove a node from a list, there are some aspects to take into account:
- list may be empty; (ii) list may contain a single node; (iii) list has more than one And, also, deletion of the first, the last or a node given by its key may be required. Thus we have the following cases:
- Removing the first node of a list
NodeT *p;
i f ( f i r s t != NULL )
{
/* non−empty l i s t*/
p = f i r s t ;
f i r s t = f irst −>next ;
free ( p ) ; /* free up memory */
i f ( f i r s t == NULL ) /* list is now empty */
last = NULL;
}
- Removing the last node of a list
NodeT *q, *q1;
q1 = NULL; /* initialize */
q = f i r s t ;
i f ( q != NULL )
{
/* non−empty list */
while ( q != last )
{ /* advance towards end */
q1 = q;
q = q−>next ;
}
i f ( q == f i r s t )
{
/* only one node */
f i r s t = last = NULL;
}
else
{
/* more than one node */
q1−>next = NULL;
last = q1;
}
free ( q ) ;
}
- Removing a node given by a key
NodeT *q, *q1;
q1 = NULL; /* initialize */
q = f i r s t ;
/* search node */
while ( q != NULL )
{
i f ( q−>key == givenKey ) break;
q1 = q;
q = q−>next ;
}
i f ( q != NULL )
{
/* found a node with supplied key */
i f ( q == f i r s t )
{
/* i s the f i r s t node */
f i r s t = f irst −>next ;
free ( q ) ; /* release memory */
i f ( f i r st == NULL )
last = NULL;
}
else
{
/* other than first node */
q1−>next = q−>next ;
i f ( q == last ) last = q1;
free ( q ) ; /* release memory */
}
}
Activity 5:
Complete deletion of single linked list
Solution:
For a complete deletion of a list, we have to remove each node of that list, i.e.
NodeT *p;
while ( first != NULL )
{
p = f i r s t ;
f i r s t = f irst −>next ;
free ( p ) ;
}
last = NULL;
Home Activities:
- Write a function that prints all nodes of a linked list in the reverse
- Write a function which reverses the order of the linked
- Write a function which rearranges the linked list by group nodes having even numbered and odd numbered value in their data part.
- Write a function which takes two values as input from the user and searches them in the If both the values are found, your task is to swap both the nodes in which these values are found. Note, that you are not supposed to swap values.
Related links
Single link list Stack AVL Trees Binary search Counting Sort
Doubly link list Queue Graphs Bubble Sort Radix sort
Circular link list Binary search tree Hashing Insertion Sort Bucket Sort
Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses
