AAD Unit4

Linked Lists
-Anjali Deshpande
Click to add Text
Memory Allocation
❑ Static Memory Allocation:
Static Memory is allocated for declared variables by the compiler. The
address can be found using the addressof operator and can be assigned to a
pointer. The memory is allocated during compile time.
❑ Dynamic Memory Allocation:

Memory allocation done at the time of execution(run time) is known as
dynamic memory allocation. Functions calloc() and malloc() support
allocating dynamic memory. In the Dynamic allocation of memory space is
allocated by using these functions when the value is returned by functions
and assigned to pointer variables.
About Linked Lists
Linked lists and arrays are similar since they both store collections of data
The array's features all follow from its strategy of allocating the memory
for all its elements in contiguous block of memory -STATIC
Linked lists use an entirely different strategy: linked lists allocate memory
for each element separately and only when necessary- DYNAMIC
A linked list is a data Structure which consists of group of nodes that
forms a sequence
Linked list comprise of group or list of nodes in which each node have
link to next node to form a chain
Very common data structure that is used to create tree, graph and other
abstract data types
Cons of Arrays
1.The size of the array is fixed.
Programmers allocate arrays which seem "large enough” This
strategy has two disadvantages: (a) most of the time there are just
20% or 30% elements in the array and 70% of the space in the array
really is wasted. (b) If the program ever needs to process more than
the declared size, the code breaks.
2.Inserting (and deleting) elements into the middle of the array is
potentially expensive because existing elements need to be shifted
over to make room
Why use Linked Lists?
❑ Linked lists are appropriate when the number of data elements to
be represented in the data structure at once is unpredictable
❑ Linked lists are dynamic, so the length of a list can increase or
decrease as necessary
❑ Each node does not necessarily follow the previous one
physically in the memory
❑ Linked lists can be maintained in sorted order by inserting or
deleting an element at the proper point in the list
Linked Lists
A B C 
Head
A linked list is a series of connected nodes

Each node contains at least
A piece of data (any type)
Pointer to the next node in the list
Head: pointer to the first node node
The last node points to NULL A
data pointer
A Simple Linked List Class
We use two classes: Node and List
Declare Node class for the nodes
data: double-type data in this example
next: a pointer to the next node in the list
class Node {
public:
double data; // data
Node* next; // pointer to next
};
Declare List, which contains
head: a pointer to the first node in the list.
Since the list is empty initially, head is set to NULL
Operations on List
class List {
public:
List(void) { head = NULL; } // constructor
~List(void); // destructor
bool IsEmpty() { return head == NULL; }

Node* InsertNode(int index, double x);
int FindNode(double x);
int DeleteNode(double x);
void DisplayList(void);
private:
Node* head;
};
Operations of List
IsEmpty: determine whether 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
Inserting a new node
Node* InsertNode(int index, double x)
Insert a node with data equal to x after the index’th elements.
(i.e., when index = 0, insert the node as the first element;
when index = 1, insert the node after the first element, and so on)
If the insertion is successful, return the inserted node.
Otherwise, return NULL.
(If index is < 0 or > length of the list, the insertion will fail.)
Steps
index’th
1. Locate index’th element element
2. Allocate memory for the new node

3. Point the new node to its successor
4. Point the new node’s predecessor to the new node
newNode
Possible cases of InsertNode

1. Insert into an empty list
2. Insert in front
3. Insert at back
4. Insert in middle
But, in fact, only need to handle two cases
Insert as the first node (Case 1 and Case 2)
Insert in the middle or at the end of the list (Case 3 and
Case 4)
Node* List::InsertNode(int index, double x) { Try to locate
if (index < 0) return NULL; index’th node. If it
doesn’t exist,
int currIndex = 1;
return NULL.
Node* currNode = head;
while (currNode && index > currIndex) {
currNode = currNode->next;
currIndex++;
}
if (index > 0 && currNode == NULL) return NULL;
Node* newNode = new Node;

newNode->data = x;
if (index == 0) {
newNode->next = head;
head = newNode;
}
else {
newNode->next = currNode->next;
currNode->next = newNode; }
return newNode;}
Node* List::InsertNode(int index, double x) {
if (index < 0) return NULL;
int currIndex = 1;
currIndex++;
}

newNode->data = x;
if (index == 0) {
Create a new node
head = newNode;
}
else {
currNode->next = newNode;
}
int currIndex = 1;
currIndex++;
}

newNode->data = x;
Insert as first element
if (index == 0) { head
head = newNode;
}
else {
newNode->next = currNode->next; newNode
}
return newNode;
}
int currIndex = 1;
currIndex++;
}

newNode->data = x;
if (index == 0) {
head = newNode; Insert after currNode
}
currNode
else {
}
return newNode;
} newNode
Finding a node
int FindNode(double x)
Search for a node with the value equal to x in the list.
If such a node is found, return its position. Otherwise, return 0.
int List::FindNode(double x) {
int currIndex =1;
while (currNode && currNode->data != x) {
currIndex++;
}
if (currNode) return currIndex;
return 0;
}
Deleting a node
int DeleteNode(double x)
❑ Delete a node with the value equal to x from the list.
❑ If such a node is found, return its position. Otherwise, return 0.
Steps
❑ Find the node (similar to FindNode)
❑ Release the memory occupied by the found node
❑ Set the pointer of the predecessor of the found node to the
successor of the found node
Like InsertNode, there are two special cases
❑ Delete first node
❑ Delete the node in middle or at the end of the list
Deleting a node
int List::DeleteNode(double x) {
Node* prevNode = NULL;
Try to find the node with
Node* currNode = head; its value equal to x
int currIndex = 1;
prevNode = currNode;
currIndex++;
}
if (currNode) {
if (prevNode) {
prevNode->next = currNode->next;
delete currNode;
}
else {
head = currNode->next;
delete currNode;
}
return currIndex;
}
return 0;
}
Deleting a node
int currIndex = 1;
currIndex++; prevNode currNode
}
if (currNode) {
if (prevNode) {
delete currNode;
}
else {
delete currNode;
}
return currIndex;
}
return 0;
}
Deleting a node
int currIndex = 1;
currIndex++;
}
if (currNode) {
if (prevNode) {
delete currNode;
}
else {
delete currNode;
}
return currIndex;
} head currNode
return 0;
}
Printing all the elements
void DisplayList(void)
Print the data of all the elements
Print the number of the nodes in the list
void List::DisplayList()
{
int num = 0;
while (currNode != NULL){
cout << currNode->data << endl;
num++;
}
cout << "Number of nodes in the list: " << num << endl;
}
Destroying the list
~List(void)
Use the destructor to release all the memory used by the list.
Step through the list and delete each node one by one.
List::~List(void) {
Node* currNode = head, *nextNode = NULL;
while (currNode != NULL)
{
nextNode = currNode->next;
// destroy the current node
delete currNode;
currNode = nextNode;
}
}
result
Using List
int main(void)
{
List list;
list.InsertNode(0, 7.0); // successful
list.InsertNode(-1, 5.0); // unsuccessful
list.InsertNode(8, 4.0); // unsuccessful
// print all the elements
list.DisplayList();
if(list.FindNode(5.0) > 0) cout << "5.0 found" << endl;
else cout << "5.0 not found" << endl;
list.DeleteNode(7.0);
list.DisplayList();
return 0;
}
6
7 result
Using List
5
Number of nodes in the list: 3
5.0 found
4.5 not found
6
int main(void) 5
{ Number of nodes in the list: 2
List list;
list.InsertNode(-1, 5.0); // unsuccessful
list.InsertNode(8, 4.0); // unsuccessful
// print all the elements
list.DisplayList();
list.DeleteNode(7.0);
list.DisplayList();
return 0;
}
Variations of Linked Lists
Circular linked lists
The last node points to the first node of the list
A B C
Head
How do we know when we have finished traversing

the list? (Tip: check if the pointer of the current
node is equal to the head.)
Variations of Linked Lists
Doubly linked lists
Each node points to not only successor but the
predecessor
There are two NULL: at the first and last nodes in
the list
Advantage: given a node, it is easy to visit its
predecessor. Convenient to traverse lists backwards
 A B C 
Head
Array versus 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.
Circular Linked List
1. Circular Singly Linked List
In Circular Singly Linked List, each node has just one pointer
called the “next” pointer. The next pointer of last node points
back to the first node and this results in forming a circle. In this
type of Linked list, we can only move through the list in one
direction.
2. Circular Doubly Linked List:
In circular doubly linked list, each node has two pointers prev
and next, like doubly linked list. The prev pointer points to the
previous node and the next points to the next node. Here, in
addition to the last node storing the address of the first node, the
first node will also store the address of the last node.
Structure of Circular Singly Linked
List:
1. Node Class: This will represent a
node in the list, containing data
and a pointer to the next node.
2. LinkedList Class: This will
manage the operations such as
insertion, deletion, and display.
class Node class CircularLinkedList
{public: {private:
int data; Node* last;
Node* next; public:
Node(int value) CircularLinkedList() {
last = nullptr; }
{data = value;
next = nullptr; }};
1.At the beginning.
❑ To insert a new node at the beginning of a circular linked list, we first
create the new node and allocate memory for it.
❑ If the list is empty (indicated by the last pointer being NULL), we
make the new node point to itself.
❑ If the list already contains nodes then we set the new node’s next
pointer to point to the current head of the list (which is last->next),
and then update the last node’s next pointer to point to the new
node. This maintains the circular structure of the list.
1.At the beginning.
At the end
❑ To insert a new node at the end of a circular linked list, we first create the
new node and allocate memory for it.
❑ If the list is empty (mean, last or tail pointer being NULL), we initialize the
list with the new node and making it point to itself to form a circular
structure.
❑ If the list already contains nodes then we set the new node’s next pointer to
point to the current head (which is tail->next), then update the current tail’s
next pointer to point to the new node. Finally, we update the tail pointer to
the new node. This will ensure that the new node is now the last node in the
list while maintaining the circular linkage.
At the end
Delete at the beginning.
❑ To delete the first node of a circular linked list, we first check if the list is
empty.
❑ If it is then we print a message and return NULL.
❑ If the list contains only one node (the head is the same as the last) then we
delete that node and set the last pointer to NULL.
❑ If there are multiple nodes then we update the last->next pointer to skip the
head node and effectively removing it from the list. We then delete the head
node to free the allocated memory. Finally, we return the updated last
pointer, which still points to the last node in the list.
Delete at the beginning.
Delete at the end
❑ To delete the last node in a circular linked list, we first check if the list is
empty. If it is, we print a message and return nullptr.
❑ If the list contains only one node (where the head is the same as the last), we
delete that node and set last to nullptr.
❑ For lists with multiple nodes, we need to traverse the list to find the second
last node.
❑ We do this by starting from the head and moving through the list until we
reach the node whose next pointer points to last. Once we find the second
last node then we update its next pointer to point back to the head, this
effectively removing the last node from the list. We then delete the last node
to free up memory and return the updated last pointer, which now points to
the last node.
Delete at the end
Display the nodes
Doubly linked List
❑ A doubly linked list is a data structure that consists of a set of nodes, each of
which contains a value and two pointers, one pointing to the previous node
in the list and one pointing to the next node in the list.
❑ This allows for efficient traversal of the list in both directions, making it
suitable for applications where frequent insertions and deletions are
required.
Doubly linked List
Insertion at the Beginning
To insert a new node at the front of doubly linked list,
❑ Create a new node, say new_node with its previous pointer as NULL.
❑ Set the next pointer to the current head, new_node->next = head.
❑ Check if the linked list is not empty then we update the previous pointer of the
current head to the new node, head->prev = new_node.
❑ Finally, we return the new node as the head of the linked list.
Insertion at the End
To insert a new node at the end,
❑ Allocate memory for a new node, say new_node and assign the provided value
to its data field.
❑ Initialize the next pointer of the new node to NULL, new_node->next = NULL.
❑ If the linked list is empty, we set the new node as the head of linked list and
return it as the new head of the linked list.
❑ Traverse the entire list until we reach the last node, say curr.
❑ Set the next pointer of last node to new node, curr->next = new_node
❑ Set the prev pointer of new node to last node, new_node->prev = curr
Deletion at the Beginning
The idea is to update the head of the doubly linked list to the node next to head node and
if the new head is not NULL, then set the previous pointer of new head to NULL.
To delete a node at the beginning in doubly linked list, we can use the following steps:
❑ Check if the list is empty, there is nothing to delete, return.
❑ Store the head pointer in a variable, say temp.
❑ Update the head of linked list to the node next to the current head,
head = head->next.
❑ If the new head is not NULL, update the previous pointer of new head to NULL,
head->prev = NULL.
Deletion at the End
To delete a node at the end in doubly linked list, we can use the following steps:
❑ Check if the doubly linked list is empty. If it is empty, then there is nothing to
delete.
❑ If the list is not empty, then move to the last node of the doubly linked list, say
curr.
❑ Update the second-to-last node’s next pointer to NULL, curr->prev->next =
NULL.
❑ Free the memory allocated for the node that was deleted.
Doubly Circular Linked List
To insert a new node at the front of a doubly circular linked list,

1. Allocate memory for the new node.
2. If the list is empty, set the new node’s next and prev to point to
itself, and update the head to this new node.
3. For a non-empty list, insert the new node:
1. Set the new node’s next to the current head.
2. Set the new node’s prev to the last node.
3. Update the current head’s prev to the new node.
4. Update the last node’s next to the new node.
4. Set the new node as the new head of the list.
To insert a new node at the end of doubly circular linked list,

1. Allocate memory for the new node.
2. If the list is empty, set the new node’s next and prev pointers to
point to itself, and update the head to this new node.
3. For a non-empty list, insert the new node:
1. Find the current last node (the node whose next pointer points to the head).
2. Set the new node’s next pointer to point to the head.
3. Set the new node’s prev pointer to point to the current last node.
4. Update the current last node’s next pointer to point to the new node.
5. Update the head’s prev pointer to point to the new node.
Polynomial Manipulation
• Polynomial manipulations are one of the most important applications of
linked lists.
• A polynomial is a collection of different terms, each comprising
coefficients, and exponents.
• It can be represented using a linked list. This representation makes
polynomial manipulation efficient.
• While representing a polynomial using a linked list, each polynomial
term represents a node in the linked list.
• To get better efficiency in processing, we assume that the term of
every polynomial is stored within the linked list in the order of
decreasing exponents.
• Also, no two terms have the same exponent, and no term has a zero
coefficient and without coefficients. The coefficient takes a value of 1.
Each node of a linked list representing polynomial constitute three parts:
• The first part contains the value of the coefficient of the term.
• The second part contains the value of the exponent.
• The third part, LINK points to the next term (next node).
• Consider a polynomial P(x) = 7x4 + 15x3 - 2 x2 + 9. Here 7, 15, -2, and

9 are the coefficients, and 4,3,2,0 are the exponents of the terms in the
polynomial. On representing this polynomial using a linked list, we have
• To add two polynomials, we can add the coefficients of like terms and
generate a new linked list for the resulting polynomial. For example, we
can use two liked lists to represent polynomials 2-4x+5x^2 and 1+2x -
3x^3:
• When we add them together, we can group the like terms and generate
the result 3 - 2x^2 + 5x^2 - 3x^3:
In this algorithm, we first create two pointers, p1 and p2, to the head
pointers of the two input polynomials. Then, we generate the new
polynomial nodes based on the powers of these two pointers. There are
three cases:
1. p1‘s power is greater than p2‘s power: In this case, we append a new
node with p1‘s power and coefficient. Also, we move p1 to the next
node.
2. p2‘s power is greater than p1‘s power: In this case, we append a new
node with p2‘s power and coefficient. Also, we move p2 to the next
node.
3. p1 and p2 have the same power: In this case, the new coefficient is
the total of p1‘s coefficient and p2‘s coefficient. If the new coefficient is
not 0, we append a new node with the same power and the new
coefficient. Also, we move both p1 and p2 to the next nodes.
After that, we continue to append the remaining nodes from p1 or p2 until
we finish the calculation on all nodes.
The append function can create a new linked list node based on the input
power and coefficient. Also, it appends the new node to the tail node
and returns the new tail node:
Generalized Linked List
• In GLL, there is a need of an extra field called
as tag to indicate whether the element is an
atom or a sublist
• Tag field contains value either 0 or 1
• 1 indicates sublist
• 0 indicates atom
• When the node represents a sublist, then it
stores address of first element of the sublist
Data or
Tag Pointer
Down Pointer
EXAMPLES…
Why Generalized Linked List?
• Generalized linked lists are used because

although the efficiency of polynomial operations
using linked list is good but still, the disadvantage
is that the linked list is unable to use multiple
variable polynomial equation efficiently.
• It helps us to represent multi-variable polynomial
along with the list of elements.
Polynomial Representation using GLL
• Here Flag = 0 means variable is present

• Flag = 1 means down pointer is present
• Flag = 2 means coefficient and exponent is
present
Example: 9x5 + 7x4y + 10xz
Example: 12p2 + 5q10r+ 9t

AAD Unit4

Uploaded by

Copyright:

Available Formats

AAD Unit4

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

AAD Unit4

Uploaded by

Copyright:

Available Formats

Linked Lists

❑ Dynamic Memory Allocation:

A linked list is a series of connected nodes

bool IsEmpty() { return head == NULL; }

2. Allocate memory for the new node

Possible cases of InsertNode

Node* newNode = new Node;

Node* newNode = new Node;

Node* newNode = new Node;

Node* newNode = new Node;

How do we know when we have finished traversing

Linked lists are more complex to code and manage

To insert a new node at the front of a doubly circular linked list,

To insert a new node at the end of doubly circular linked list,

• Consider a polynomial P(x) = 7x4 + 15x3 - 2 x2 + 9. Here 7, 15, -2, and

• Generalized linked lists are used because

• Here Flag = 0 means variable is present

You might also like