Description
-
Linked Lists
A linked list is an abstract data structure that stores a list, where each element in the list points to the next element.
Let us elaborate:
Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after the array. Following are the important terms to understand the concept of Linked List.
-
Node!”!#$%&!'()*!(+!$!,-./*)!,-01!%$.!01(2*!)$1$!$.)!$!,-./3
-
Link!”!#$%&!'()*!(+!$!,-./*)!,-01!%(.1$-.0!$!,-./!1(!1&*!.*41!'()*!56.-1!(+!7-./*)!7-0189! (+1*.!%$,,*)!:.*41;!-.!%()*3
-
Linked List!”!<!7-./*)!7-01!%(.1$-.0!$!%(..*%1-(.!,-./!+2(=!1&*!+-201!,-./!%$,,*)!>*$)3! #?*2@!7-./!$+1*2!1&*!&*$)!A(-.10!1(!$.(1&*2!'()*!56.-1!(+!7-./*)!7-0183!B&*!,$01!.()*! A(-.10!1(!’C773!D(=*1-=*09!1&*!+-201!.()*!(+!1&*!7-./*)!7-01!-0!12*$1*)!$0!1&*!&*$)3!
Recitation 4, Spring 2022
Linked List Operations
1
Data next
Head
2
Data next
3
Data next
4
Data next
NULL
In code, each node of the linked list will be represented by a class or struct. These contain, at a minimum, two pieces of information – the data that node contains, and a pointer to the next node. Example code to create these is below:
You can base your Linked List on a class or a struct, we prefer you stick to class.
class Node
{
public:
int data;
Node *next;
};
struct node
{
int data;
Node *next;
};
1.a Types of Linked Lists
The one seen above is called a Singly Linked List. You will also work with Doubly Linked Lists where each Node has a pointer to its next as well as its previous Node, and Circular Linked Lists, where the last Node points to the head of the Linked List.
The Two Linked Lists are shown below.
Recitation 4, Spring 2022
Linked List Operations
2. Insertion
Adding a new node to a Linked List is a multi-step activity. For your understanding, we have visualizations. First, you must create a new node that is of the SAME datatype as the other nodes of the Linked List. Then, find the location where it must be inserted.
Different scenarios of insertion
-
-
Inserting at the beginning of the Linked List.
-
-
-
Inserting at the end of the Linked List.
-
-
-
Inserting at any given position.
-
-
Inserting at the beginning.
The following diagram shows a Linked List with 4 nodes (1, 2, 3, and 4). And a node with data 0 is inserted at the beginning of the Linked List. The steps are as follows.
-
Create a new node with data 0.
-
Update its next pointer to point to the beginning of the Linked List. This is done by making it point to the head.
-
Now, update the head pointer to point to the new node.
Recitation 4, Spring 2022
Linked List Operations
1
Data next
0
Head
2
Data next
3
Data next
4
Data next
NULL
B. Inserting at any given position.
For the same Linked List (4 nodes – 1, 2, 3, 4), we would like to insert the Node B with data 0, after A and before C. For this, we follow the steps below.
-
Create the new node B with data 0 in it, and make its next pointer point to NULL.
-
By getting the location of the first node (Head), traverse the Nodes of the Linked List until the Node with data 2 is found.
-
We must not lose the address of Node C which is stored in the next pointer of Node A. Therefore, we store this address in a temporary variable.
-
We can safely update Node A’s next pointer to point to the address of Node B.
-
Finally, we make the B’s next pointer to point to the address of Node C that is stored in the temporary variable.
1
Data next
Head
A
2
Data
temp
C
3
next
B
0
4
Data next
NULL
Recitation 4, Spring 2022
Linked List Operations
C. Inserting at the end
Yet again, for the same Linked List (4 Nodes with 1, 2, 3, 4), we would like to insert Node B, at the end of the Linked List. For this, we follow the steps below.
next
-
Create the new node B with the data 9 in it, and make its next pointer point to NULL.
-
Beginning at the Head node, traverse the Linked List till you find a node with its next pointer pointing to NULL.
-
Update this pointer to point to the address of node B.
1
Data next
Head
2
Data next
Data
3 next
Data next
|
A |
|||
|
4 |
NULL |
||
|
Data |
|||
|
next |
|||
9
B
Note: It is always a good practice to make a new node’s next pointer to initially point to NULL.
2. Traversal and printing
To print the elements of the Linked List, we start from its head and traverse every node. The traversal is done by using the next pointer which points to the next element of the Linked List. This traversal is done until the next pointer no longer points to a node (i.e., NULL). In a Circular Linked List, this traversal is done until the next pointer points to the Head.
Recitation 4, Spring 2022
Linked List Operations
-
Quizzes (DO NOT have to submit)
-
-
Why do we need to use Linked list instead of Array?
-
-
-
What kind of memory allocation do we need to do for Linked lists?
-
-
-
-
Compile time allocation
-
-
-
-
-
Run time allocation
-
-
-
-
What does “Head” mean in a Linked list?
-
-
-
Any practical examples of Linked lists that we use in our daily life?
-
-
Exercise
Download the Recitation 4.zip folder from Canvas. There are LinkedList header, implementation, and main files.
Your task is to complete the following function/functions:
-
Complete the insert and search functions.(Silver problem – Mandatory )
-
Swap the first and last nodes in a linked list (Gold problem-Optional)
Submission: Once you’ve completed the exercises, zip all the files up and submit on the Canvas link. Name the submission in the following format: recitation4_firstname_lastname.zip
