DATA STRUCTURES AND

ALGORITHMS

Linked List

1
 Remember Arrays…
Static Array:
◦ char a[10];
◦ Size must explicitly be mentioned at declaration
Once declared the size
Dynamic Array: cannot be changed !!!
◦ char *p;
◦ p = new char[10];
◦ Size can be declared at run time

An array cannot shrink or

grow!!!

https://www.geeksforgeeks.org/introduction-to-arrays/ 2
Array vs. Linked List
Linked list does not require explicit mention of size at declaration
It can easily shrink and grow as per requirement

www.interviewbit.com 3
An Array A Linked List

4
 Arrays Vs Lists
• Arrays are lists that have a fixed size in memory.
• The programmer must keep track of the length of the
array
• No matter how many elements of the array are used
in a program, the array has the same amount of
allocated space.
• Array elements are stored in successive memory
locations. Also, order of elements stored in array is
same logically and physically.

5
 Arrays Vs Lists
• A linked list takes up only as much space in memory
as is needed for the length of the list.
• The list expands or contracts as you add or delete
elements.
• In linked list the elements are not stored in successive
memory location
• Elements can be added to (or deleted from) either
end, or added to (or deleted from)the middle of the
list.

6
 Array vs Linked Lists
Linked lists are more complex to code and manage than
arrays, but they have some distinct advantages.
◦ Dynamic: a linked list can easily grow and shrink in size.
◦ We don’t need to know how many nodes will be in the list. They are created in
memory as needed.
◦ In contrast, the size of a C++ array is fixed at compilation time.
◦ Easy and fast insertions and deletions
◦ To insert or delete an element in an array, we need to copy to temporary
variables to make room for new elements or close the gap caused by deleted
elements.
◦ With a linked list, no need to move other nodes. Only need to reset some
pointers.

7
Linked List
A list is a collection of items:
It can have an arbitrary length
Objects / elements can be inserted or removed at arbitrary locations in
the list
A list can be traversed in order one item at a time

8
List as an ADT
A list is a finite sequence (possibly empty) of elements with
basic operations that vary from one application to another.

Basic operations commonly include:

◦ Construction: Allocate and initialize a list object (usually
empty)
◦ Empty: Check if list is empty
◦ Insert: Add an item to the list at any point
◦ Delete: Remove an item from the list at any point
◦ Traverse: Visiting each node of list

9
Variations of linked lists
Singly linked lists

Circular linked lists

Doubly linked lists

Circular doubly linked list

Linked list with dummy header node

Linked list with tail pointer

10
Linked list
Minimal Requirements
◦ Locate the first element

◦ Given the location of any list element, find its successor

◦ Determine if at the end of the list

11
 Linked List
Terminologies
Traversal of List
◦ Means to visit every element or node in the list beginning
from first to last.
Predecessor and Successor
◦ In the list of elements, for any location n, (n-1) is
predecessor and (n+1) is successor
◦ In other words, for any location n in the list, the left
element is predecessor and the right element is successor.
◦ Also, the first element does not have predecessor and the
last element does not have successor.

12
 Linked Lists
A B C 

Head

A linked list is a series of connected nodes

Each node contains at least node
◦ A piece of data (any type) A
◦ Pointer to the next node in the list
data pointer
Head: pointer to the first node
The last node points to NULL

13
Lists – Another
perspective
A list is a linear collection of varying length of
homogeneous components.

Homogeneous: All components are of the same

type.

Linear: Components are ordered in a line (hence

called Linear linked lists).

14
Basic Operations of
Linked List
Linked List, a linear collection of data items, called nodes, where order
is given y means of pointers.
Elements:
◦ Each node is divided into two parts:
◦ Information
◦ Link ( pointing towards the next node)

(Common) Operations of Linked List

◦ IsEmpty: determine whether or not the list is empty
◦ InsertNode: insert a new node at a particular position
◦ FindNode: find a node with a given value
◦ DeleteNode: delete a node with a given value
◦ DisplayList: print all the nodes in the list

15
 An integer linked list

First Node of List Last Node of List

head
10 13 5 2

data next NULL

16
Reminder: The NULL
pointer
NULL is a special pointer value that does not
reference any memory cell.

If a pointer is not currently in use, it should be set to

NULL so that one can determine that it is not
pointing to a valid address:

int *p;
p = NULL;

17
 Creating a Node To avoid get/set methods
Class Node {
Public:
int data; // data in node
Node *next; // Pointer to next node
};

//Driver.cpp:
Node *p;
p = new Node; p 10
p -> data = 10;
p -> next = NULL;

18
Deleting a Node
//Driver.cpp:
delete p;
p = NULL; p 10

19
 An integer (singly)
linked list
First Node of List Last Node of List

head
10 13 5 2

data next NULL

class Node {
public:
int data;
Node *next;
};

20
Joining two nodes
Node *p, *q;

p = new Node; p 10
p - > data = 10;
p - > next = NULL;

q = new Node;
q - > data = 6; q 6
q - > next = NULL;

p - > next = q;
p 10 6

q 21
Accessing List Data

p 10 6

Expression Value
p Pointer to first node (head)
p - > data 10
p - > next Pointer to next node
p - > next - > data 6
p - > next - > next NULL pointer

22
Basic Concepts
Building a list from 1 to
n
class Node {
public:
int data;
Node *next;
};

Node *head = NULL; // pointer to the list head

head

24
Basic Concepts

Creating the first node

Node *ptr, *ptr2; // declare two pointer to Node
ptr = new Node; // create a new Node
ptr - > data = 1;
ptr - > next = NULL;

head = ptr; // new node is first

head 1
ptr

ptr2
25
Basic Concepts

Adding more nodes

for (int i = 2; i < = n; i ++ ) {
ptr2 = new Node;
ptr2 - > data = i;
ptr2 - > next = NULL;
ptr - > next = ptr2; // order is
ptr = ptr2; // important
}

head 1 2
ptr
ptr2
26
head 1 2

ptr

ptr2 3

•Create a new node with data field set to 3

•Its next pointer should point to NULL

27
 head 1 2

ptr

ptr2 3
The next pointer of the node which was
previously last should now point to newly
created node “ptr->next=ptr2”

28
 head 1 2

ptr

ptr2 3

ptr should now point to the newly created Node

“ptr = ptr2;”

29
 Re-arranging the view

head 1 2 3
ptr
ptr2

30
Basic linked list
operations
Traversing through the list
Node Insertion
◦ Insertion at the beginning of the list
◦ Insertion at the end of the list
◦ Insertion in arbitrary location of the list

Node Deletion
◦ Deletion at the beginning of the list
◦ Deletion at the end of the list
◦ Deletion from the arbitrary location of the list

31
Traversing the list

32
Traversing the list
ptr = first;
while (ptr != null_value)
{
Process data part of node pointed to by ptr
ptr = next part of node pointed to by ptr;
}

33
 first 9 17 22 26 34

ptr
ptr = first;
while (ptr != null_value) first 9 17 22 26 34
{
Process data part of
node pointed to by ptr; ptr
ptr = next part of node .
.
pointed to by ptr;
.
}
first 9 17 22 26 34

ptr

first 9 17 22 26 34

ptr

34
Traversing the list
Node *currNode;
currNode = head;
while (currNode != NULL)
{
cout<< currNode->data;
currNode = currNode->next;
}

35
Node insertion
Insertion at the beginning of the list
Insertion at the end of the list
Insertion in arbitrary location in a the list

36
 Node insertion at the
beginning
Steps:
Create a node
Set the node data values
Connect the pointers

Initial list head 48 17 142 //

Step 1 Step 2

List after Step 3

head 93
Node insertion at the
beginning
Initial list head 48 17 142 //

Node *ptr;
ptr = new Node; ptr
ptr - > data = 93;
ptr - > next = head; ptr
head = ptr; 93
head

head
Rearrange:

head 93
 Node insertion at the
Steps: end
Create a Node
Set the node data values
Connect the pointers

Initial list head 48 17 142 //

Step 1 Step 2

List after Step 3

end
Initial list head 48 17 142 //
Need a pointer at the last node
ptr

Node * ptr;
ptr = head;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
end
Initial list head 48 17 142 //

ptr

Node * p;
p = new Node;
p -> data = 150; 150 //
p -> next = NULL;
p
end
Node * p;
p = new Node;
p -> data = 150;
p -> next = NULL;
ptr -> next = p;
ptr

head 48 17 142

150 //
p
 Node
Steps:
insertion at arbitrary position
Create a Node
Set the node data values Step 1 Step 2
Break pointer connection
Re-connect the pointers

Step 3

Step 4
 Node insertion at arbitrary
position
Steps:
Create a Node
Set the node data values
Break pointer connection
Re-connect the pointers
Need a pointer on the node after which a new node is to be
Inserted. For instance, if new node is to be inserted after the node
having value ‘17’, we need a pointer at this node

ptr
How to get pointer on desired node?
Node insertion at arbitrary
position
Suppose we want to insert a node after the node having value ‘x’:

Node * ptr;
ptr = head;
while (ptr->data != x)
{
ptr = ptr->next;
}

ptr
Node insertion at arbitrary
position
Node * ptr; Node * p;
p = new Node;
ptr = head;
p -> data = 100;
while (ptr->data != x)
p -> next = NULL;
{
ptr = ptr->next;
}

ptr

150 //
p
Node insertion at arbitrary
position
Node * ptr; Node * p;
p = new Node;
ptr = head;
p -> data = 100;
while (ptr->data != x)
p -> next = NULL;
{ p -> next = ptr -> next;
ptr = ptr->next; ptr -> next = p;

ptr

150

p
Node Deletion
Deleting from the beginning of the list

Deleting from the end of the list

Deleting from the middle of the list

 beginning
Steps:
Break the pointer connection
Re-connect the nodes
Delete the node

head 6 4 17 42

head
6 4 17 42

head 4 17 42
beginning
head
ptr 6 4 17 42

head
head 6 4 17 42
ptr

head 4 17 42

Node * ptr;
ptr = head;
head = head ->next;
delete ptr;
Deleting from the end
Steps:
Break the pointer connection
Set previous node pointer to NULL
Delete the node

head 6 4 17 42

head 6 4 17 42

head 6 4 17
Deleting from the end
We need a pointer one node before the node to be deleted

head 6 4 17 42

predPtr ptr
Node * ptr;
Node * predPtr;
ptr = head;
predPtr = NULL;
while (ptr->next != NULL)
{
predPtr = ptr;
ptr = ptr->next;

}
Deleting from the end
head 6 4 17 42

predPtr ptr

head 6 4 17 42

predPtr ptr

head 6 4 17 42

predPtr ptr

head 6 4 17

predPtr -> next = NULL;

delete ptr;
 Deleting from an arbitrary
position
Steps:
Set previous Node pointer to next node
Break Node pointer connection
Delete the node

head 4 17 42

head 4 17 42

head 4 42
Deleting from an arbitrary
position
We need a pointer on the node to be deleted (as well a pointer to one node
before the node to be deleted)

head 4 17 42

predPtr ptr

Node * ptr;
Node * predPtr;
Given the value of the node to be
ptr = head;
deleted, assume this to be variable ‘x’
predPtr = NULL; Keep moving a pointer until the
while (ptr->data != x) required node is reached
{
predPtr = ptr;
ptr = ptr->next;

}
Deleting from an arbitrary
position
head 4 17 42

predPtr ptr

head 4 17 42

predPtr ptr

head 4 17 42

predPtr ptr
predPtr -> next = ptr -> next;
delete ptr;
 Pros and cons of linked
lists
• Access any item as long as external link to first item maintained
• Insert new item without shifting
• Delete existing item without shifting
• Can expand/contract as necessary
• Overhead of links: used only internally, pure overhead
• No longer have direct access to each element of the list
• We must go through first element, and then second, and then third,
etc.

57
Implementing Linked Lists in C++

To Implement Nodes
typedef DataType int;

class Node
{
public:
DataType data;
Node * next;
};

Note: The definition of a Node is a recursive (or self-referential)

definition because it uses the name Node in its definition:
the next member is defined as a pointer to a Node .

58
The linked list class
class List
{
private:
Node * head;
public:
List();
~List();
bool emptyList();
void insertafter(DataType oldV, DataType newV);
void deleteItem(DataType value);
void insert_begin(DataType value);
void insert_end(DataType value);
};

59
// Default Constructor that initializes a newly
created list to empty list.
List::List()
{
head = 0;
}

// Destructor traverses the nodes of a list, freeing

them one by one.
List::~List()
{
Node * p, *q;
if (emptyList())
exit(0);
p = head;
q = p->next;
while (p!=0)
{
delete p;
p = q;
if(p!=0)
q = p->next;
}
}

60
// Determines if the list is empty.

bool List::emptyList()
{
if (head == 0)
return true;
else
return false;
}

61
// searches for the first occurrence of ‘oldV’ in the
list and inserts a new node with value
‘newV’following the node containing ‘oldV’

void List::insertafter(DataType oldV, DataType newV)

{
Node *p, *q;
p = head;
while(p!=0 && p->data!= oldV)
p = p->next;
if (p == 0)
{ cout << " ERROR: Value sought is not in the
list.";
exit(1);
}

q = new Node;
q->data = newV;
q->next = p->next;
p->next = q;
} 62
//Deletes the first node containing ‘value’
void List::deleteItem(DataType value)
{
Node *p, *q;
q =0;
p = head;
while (p!=0 && p->data != value)
{
q = p;
p = p->next;
}
if (p == 0)
{ cout << "ERROR: Value sought not found.";
exit(1);
}
if (q == 0)
head = p->next;
else
q->next = p->next;
delete p;
} 63
//Inserts a node in the beginning of the list
void List::insert_begin(DataType value)
{
Node *temp, *p;
temp = new Node;
temp->data = value;
temp->next = NULL;

if (head == 0)
{
head = temp;
head->next = 0;
}
else
{
p = head;
head = temp;
head->next = p;
}

64
//Inserts a node at the of the list

void List::insert_end(DataType value)

{
Node *temp, *p;
temp = new Node;
temp->data = value;
temp->next = NULL;

p = head;
while (p->next != 0)
{
p = p->next;
}
temp->next = 0;
p->next = temp;

65
While vs. for loop for
node traversal
Node* p = head;
while (p->next != 0)
{
p = p->next;
}

Node *p;
for ( p=head; p->next!= 0; p = p->next)
;

66