0% found this document useful (0 votes)

18 views53 pages

04 - LinkedLists

The document discusses linked lists and their advantages over arrays. It describes how linked lists are composed of nodes that contain a data element and a pointer to the next node. The key operations for linked lists include inserting and deleting nodes. As an example, it provides code for a FloatList class that implements a singly linked list with functions for appending nodes, displaying the list, and deleting nodes. The appendNode function allocates a new node, sets its data and next pointer, and either makes it the head node or links it to the last node in the list.

Uploaded by

Muhammad Owais khan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

18 views53 pages

04 - LinkedLists

Uploaded by

Muhammad Owais khan

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 53

Data Structures & Algorithms

Linked Lists
Today‘s lecture

▪ Linked structures
► Singly Linked Lists

Lecture 4: Linked Lists 2

Linked List Concepts

▪ Data is stored dynamically

► Each node is created as necessary

▪ Nodes of linked lists are not necessarily stored

contiguously in memory (as in an array)

▪ Although lists of data can be stored in arrays, linked

lists provide several advantages

Lecture 4: Linked Lists 3

Advantages of Linked Lists

▪ The size of a “conventional” C++ array cannot be

altered because the array size is fixed at compile time
▪ Also, arrays can become full (i.e., all elements of the
array are occupied)
Advantage 1: Dynamic
▪ A linked list is appropriate when the number of data
elements to be stored in the list is unknown
▪ Because linked lists are dynamic, their size can grow
or shrink to accommodate the actual number of
elements in the list
▪ A linked list is full only when the computer runs out of
memory in which to store nodes
Lecture 4: Linked Lists 4
Advantages of Linked Lists

Advantage 2: Easy Insertions and Deletions

▪ Although arrays are easy to implement and use, they

can be quite inefficient when sequenced data needs to
be inserted or deleted.

▪ With arrays, it is difficult to rearrange data (copying to

temporary variables, etc.)

▪ However, the linked list structure allows us to easily

insert and delete items from a list

Lecture 4: Linked Lists 5

Disadvantages of Linked Lists

▪ Unfortunately, linked lists are also not without

drawbacks:

► For example, we can perform efficient searches on

arrays (e.g., binary search) but this is not practical with a
linked list.

Lecture 4: Linked Lists 6

Linked List Composition

▪ A linked list is called "linked" because each node in the

series has a pointer that points to the next node in the
list

▪ I.e., every node contains a data member that is a

pointer to another node allowing many nodes to be
strung together and accessed using only one variable

▪ If a node has a link only to its successor in the

sequence, the list is then called a singly linked list

Lecture 4: Linked Lists 7

Declarations in Singly Linked List

▪ First you must declare a data structure that will be used

for the nodes

► E.g., the following struct could be used to create a list

where each node holds a float:

struct ListNode {
float value;
struct ListNode *next;
};

Lecture 4: Linked Lists 8

Declarations in Singly Linked List

▪ The next step is to declare a pointer to serve as the list

head, as shown below.
ListNode *head;
▪ Once you have declared a node data structure and
have created a NULL head pointer, you have an empty
linked list.
▪ The next step is to implement operations with the list.

Lecture 4: Linked Lists 9

Linked List Operations

▪ Creating the list

► Initialize pointers to NULL;
▪ Inserting nodes
► Insert at beginning
► Insert at middle
► Insert at last
▪ Deleting nodes
► Delete from beginning, middle, last
▪ Traversing the list
▪ Searching a specified item in the list
▪ Destroying the list

Lecture 4: Linked Lists 10

//floatList.h
class FloatList {
private:
// Declare a structure for the list
struct ListNode {
float value;
struct ListNode *next;
};
ListNode *head; // List head pointer
public:
FloatList(void) { // Constructor
head = NULL;
}
~FloatList(void) { }; // Destructor
void appendNode(float);
void displayList(void);
void deleteNode(float);
};

Lecture 4: Linked Lists 11

//floatList.h
class FloatList {
private:
// Declare a structure for the list
struct ListNode {
float value;
struct ListNode *next;
};
ListNode *head; // List head pointer

public:

FloatList(void) // Constructor {
head = NULL;
}
~FloatList(void) { }; // Destructor
void appendNode(float);
void displayList(void);
void deleteNode(float);
}; Lecture 4: Linked Lists 12
Appending a node to the list

▪ To append a node to a linked list means to add the

node to the end of the list.

▪ The pseudo code is shown below:

► Create a new node.

► Store data in the new node.
► If there are no nodes in the list
- Make the new node the first node.
► Else
- Traverse the List to Find the last node.
- Add the new node to the end of the list.
► End If.
Lecture 4: Linked Lists 13
Appending a node to the list
void FloatList::appendNode(float num)
void main (void)
{
{
ListNode *newNode, *nodePtr;
FloatList list;
list.appendNode(2.5);
// Allocate a new node & store num
list.appendNode(7.9);
newNode = new ListNode;
list.appendNode(12.6)
newNode->value = num;
;
newNode->next = NULL;
}
// If there are no nodes in the list make newNode the first node
if (!head) // head == NULL
head = newNode;
else // Otherwise, insert newNode at end
{
nodePtr = head;
while (nodePtr->next) // Find the last node in the list
nodePtr = nodePtr->next;
nodePtr->next = newNode; // Insert newNode as the last node
}

Lecture 4: Linked Lists 14

Appending a node to the list
void FloatList::appendNode(float num)
void main (void)
{
{
ListNode *newNode, *nodePtr;
FloatList list;
list.appendNode(2.5);
// Allocate a new node & store num
list.appendNode(7.9);
newNode = new ListNode;
list.appendNode(12.6)
newNode->value = num;
;
newNode->next = NULL;
}
// If there are no nodes in the list make newNode the first node
if (!head) // head == NULL
head = newNode;
else // Otherwise, insert newNode at end
{ nodePtr = head;
while (nodePtr->next) // Find the last node in the list
nodePtr = nodePtr->next;

nodePtr->next = newNode; // Insert newNode as the last node

}

Lecture 4: Linked Lists 15

nodePtr->next = newNode; // Insert newNode as the last node

}

Lecture 4: Linked Lists 16

nodePtr->next = newNode; // Insert newNode as the last node

}

Lecture 4: Linked Lists 17

nodePtr->next = newNode; // Insert newNode as the last node

}

Lecture 4: Linked Lists 18

nodePtr->next = newNode; // Insert newNode as the last node

}

Lecture 4: Linked Lists 19

Appending a node to the list

Lecture 4: Linked Lists 20

Traversing the list

▪ To traverse the list we need a walking

(navigator/traversal) pointer
► This pointer is used to move from node to node as each
element is processed
► Example: displayList function….

Assign List head to node pointer.

While node pointer is not NULL
- Display the value member of the node pointed to by node
pointer.
- Assign node pointer to its own next member.
End While.

Lecture 4: Linked Lists 21

Display list

void FloatList::displayList(void)
{
ListNode *nodePtr;
nodePtr = head;

while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;

}
}

Lecture 4: Linked Lists 22

void main(void)
{
FloatList List; OUTPUT
list.appendNode(2.5); 2.5
list.appendNode(7.9); 7.9
list.appendNode(12.6); 12.6
list.displayList();
}

Lecture 4: Linked Lists 23

Deleting a node

▪ Deleting a node from a linked list requires two steps:

► Remove the node from the list without breaking the links
created by the next pointers

► Deleting the node from memory

Lecture 4: Linked Lists 24

Deleting a node

void FloatList::deleteNode(float num)

{
ListNode *nodePtr, *previousNode;
// If the list is empty, do nothing.
if (!head)
return;
// Determine if the first node is the one.
if (head->value == num) {
nodePtr = head->next;
delete head;
head = nodePtr;
}

Lecture 4: Linked Lists 25

Deleting a node

else {
// Initialize nodePtr to head of list nodePtr =
head;
// Skip all nodes whose value member is not equal to num.
while (nodePtr != NULL && nodePtr->value != num)
{
previousNode = nodePtr; nodePtr =
nodePtr->next;
}
// Link the previous node to the node after nodePtr, then delete nodePtr.
previousNode->next = nodePtr->next;
delete nodePtr;
}
}

Lecture 4: Linked Lists 26

Deleting a node

From:
http://www.tutorialspoint.com/data_structures_algorithms/data_structures_algorithms_tutorial.pdf

Lecture 4: Linked Lists 27

Insert in the middle

▪ Insert an item in the middle of the list

► Diagram/Code?

Lecture 4: Linked Lists 28

Insert in the middle

▪ Insert an item in the middle of the list

► Diagram/Code?