Introduction to Data Structures
and Algorithm
21COMP04C
2023
Lecture5
1
Labs and and tutorial
• In class test lecture 1:5 , Tutorial 1:3 and Lab 1:4
• Tutorial 3
• one hour online session (Saturday 7PM)
https://us04web.zoom.us/j/73416817706?pwd=nNtHvAGVvjSFJuwxKwagd7K
69dTjNd.1
• Lab4 submission
• Labs are ungraded
• Lab 4 submission is next Sunday
2
Our Course
Lecture Lecture Lecture Lecture
Lecture 4
1,2,3 5,6,7,8 9,10 11,12
Array Linked
OO Searching Trees
based lists lists
Pointers Template Stacks Sorting Queues
Algorithm
Recursion Graphics
analysis
Functions to Other data
Basic information First Data structure Main focus of the
process data structure
Very important course
structure
3
Lecture 5
Linked Lists
Lecture Resources
Data-Structure Using C++ by D.S. Malik (chapter 5)
These slides are adapted for the text book's slides 4
Data structures Examples
You can implement Stacks
and Queues using an array
or a linked list
Operations
Searching (find the location)
Inserting (add new element)
Deleting
Sorting
Source: https://www.hellocodeclub.com/when-to-use-which-data-structure-top-6-data-structures
5
Content
• Linked list as list of integer
• Linked list as ADT (any type of element)
Linked List
• Linked lists overcome some of the problems of list (sequential lists)
• Problem of sequential lists
• Insert and remove elements is time consuming, especially with large lists because these
operations require data movement.
• Fixed size of array
• In linked lists, we use pointers to organize and process data in lists.
FIGURE 5-2 Linked list
Array based list VS linked lists
Linked Lists: Nodes
• Linked list is a collection of components (nodes)
• Every node (except last)
• Contains address of the next node
• Node components
• Data: stores relevant information
• Link: stores address
FIGURE 5-1 Structure of a node
Data Structures Using C++ 2E 9
Linked Lists
• Linked list: A list of items, called nodes, in which the order of the nodes is
determined by the address, called the link, stored in each node.
• Every linked list has a Head (or first) [Pointer]
• Address of the first node in the list
• The arrow in each node (link) indicates that the address of the node to which
it is pointing is stored in that node.
• Down arrow in last node indicates NULL link field
FIGURE 5-2 Linked list
FIGURE 5-3 Linked list and values of the links
How to implement nodes of Linked Lists
• Because each node of a linked list has two components , we need to declare
each node as a class or struct.
• Data: data type depends on specific application
struct in page 33
• Link component: pointer
• Data type of pointer variable: node type itself
nodeType node1; nodeType *node1;
node1.info=15; node1=new nodeType;
node1.link=NULL; node1->info=15; // (*node1).info
head=&node1; node1->link=NULL;
head=node1;
cout<<head->info;
cout<<head->link
Output [15 0]
11 Static Dynamic
Linked Lists: Some Properties
• Head stores address of first node
• Info stores information
• Link stores address of next node
• Assume info type int
TABLE 5-1 Values of head and some of
the nodes of the linked list in Figure 5-4
FIGURE 5-4 Linked list with four nodes
Data Structures Using C++ 2E 12
Linked lists
• Basic operation on Linked List
• traverse a Linked List
• insert a new node to the linked lists (one pointer , two pointers)
• delete a node in linked lists
• Destroy the list
• Copy the list
Traversing a Linked List
• Basic linked list operations
• Search list to determine if particular item is in the list
• Insert item in list
• Delete item from list
• These operations require list traversal
• We cannot use the pointer head to traverse the list because if we use the
head to traverse the list, we would lose the nodes of the list.
• Therefore, we always want head to point to the first node. It now follows that
we must traverse the list using another pointer of the same type. Suppose
that current is a pointer of the same type as head
Data Structures Using C++ 2E 15
Traverse nodes in the linked list using pointer
current
Current Current Current Current Current
Access node member Moving current pointer to next node
current->info current=current->link
current->link Stop condition
current==NULL
Traverse nodes in the linked list
• we use another pointer (current)
• Pointer current: same type as pointer head
• current = head;
• Copies value of head into current
• current = current->link;
• Copies value of current->link (2800) into current
FIGURE 5-5 List after the statement
current = current->link; executes
Data Structures Using C++ 2E 17
Traversing a Linked List
• Suppose head points to a linked list of numbers
• Code outputting data stored in each node
Data Structures Using C++ 2E 18
Item Insertion using one pointer (p)
• Suppose that p points to the node with info 65, and a new node with
info 50 is to be created and inserted after p.
TABLE 5-3 Inserting a node in a linked list
The last two statements can’t be switched
Data Structures Using C++ 2E 19
Deletion
• Suppose that the node with info 34 is to be deleted from the list.
• p->link = p->link->link;
Node should be deallocated after
deleting from the list
Deletion with deallocate
• After deletion, the memory is still occupied by this node and this
memory is inaccessible;
• To deallocate the memory, we need a pointer to this node. The
following statements delete the node from the list and deallocate the
memory occupied by this node:
Destroy the list
nodeType *temp ; // need a pointer to deallocate
While (head!=NULL)
{
temp=head;
head=head->link;
delete temp;
} temp Head
Linked lists as ADT
Content
• Linked list as list of integer
• Linked list as ADT
• any type of element (int , float , char , string , course ,
student , experiments …..) ➔ template
• Abstraction (hide implementing) ➔ class
Linked lists as ADT
Empty linked list
first=Null
• Data last=Null
• First pointer (point to first element(head)) count=0
• Last pointer (point to last element)
• count integer (number of elements)
• Operations on lists List of one element
1. Initialize the list. count=1
2. Determine whether the list is empty.
3. Print the list.
4. Find the length of the list.
5. Destroy the list.
6. Retrieve the info contained in the first node.
7. Retrieve the info contained in the last node.
8. Search the list for a given item.
9. Insert an item in the list. List of 5 element
10. Delete an item from the list. count=5
11. Make a copy of the linked list.
• search, insert, and remove slightly differ for sorted and unsorted lists.
Linked List as an ADT
• class linkedListType
• Implements basic linked list operations as an ADT
• Derive two classes using inheritance
• unorderedLinkedList and orderedLinkedList
Abstract class
linkedListType • Not a complete class
• missing functions
• you cannot create objects
of that class.
unorderedLinkedList orderedLinkedList
Data Structures Using C++ 2E 26
Structure of Linked List Nodes
• Definition of the struct nodeType
Data Structures Using C++ 2E 27
Member Variables of the class
linkedListType
• class linkedListType
• Three instance variables
Data Structures Using C++ 2E 28
Convert class linkedListType
into An Abstract class by Adding
pure virtual functions
(Virtual function page 162)
Linked List
• Empty list: first is NULL
• Definition of function isEmptyList
Data Structures Using C++ 2E 31
Linked List as an ADT (cont’d.)
• Default constructor
• Initializes list to an empty state
• Destroy the list
• Deallocates memory occupied by each node
Data Structures Using C++ 2E 32
Linked List as an ADT (cont’d.)
• Initialize the list
• Reinitializes list to an empty state
• Must delete the nodes (if any) from the list
• Default constructor, copy constructor
• Initialized list when list object declared
Data Structures Using C++ 2E 33
Linked List as an ADT (cont’d.)
• Print the list
• Must traverse the list starting at first node
• Length of a list
• Number of nodes stored in the variable count
• Function length
• Returns value of variable count
Data Structures Using C++ 2E 34
Linked List as an ADT (cont’d.)
• Retrieve the data of the first node
• Function front
• Returns the info contained in the first node
• If list is empty, assert statement terminates program
• Retrieve the data of the last node
• Function back
• Returns info contained in the last node
• If list is empty, assert statement terminates program
Data Structures Using C++ 2E 35
Linked List as an ADT (cont’d.)
• Destructor
• When class object goes out of scope
• Deallocates memory occupied by list nodes
• Memory allocated dynamically
• Resetting pointers first and last
• Does not deallocate memory
• Must traverse list starting at first node
• Delete each node in the list
• Calling destroyList destroys list
Data Structures Using C++ 2E 36
Linked List as an ADT (cont’d.)
• Copy the list
• Makes an identical copy of a linked list
• Create node called newNode
• Copy node info (original list) into newNode
• Insert newNode at the end of list being created
current
While (current!=NULL)
{ first1
newNode =new nodeType;
newNode ->info=current->info;
newNode->link=NULL;
last2->link=newNode;
last2= newNode; last2 last2
current=current->link;
first2
}
Data Structures Using C++ 2E 37
Copy List (first1 and last1) to another list
from (first2 and last2)
nodeType *current ,*newNode; While (current!=NULL)
current=first1 {
newNode =new nodeType;
first2=new nodeType; newNode ->info=current->info;
first2->info=current->info; newNode->link=NULL;
first2->link=NULL; last2->link=newNode;
last2=first2; last2= newNode;
current=current->link;
current=current->link
}
Linked List as an ADT (cont’d.)
• Copy constructor
• Makes identical copy of the linked list
• Function copyList checks whether original list empty
• Checks value of first
• Must initialize first to NULL
• Before calling the function copyList
• Overloading the assignment operator
• Similar to copy constructor definition
Data Structures Using C++ 2E 40
TABLE 5-6 Time-complexity of the operations of the
class linkedListType
Data Structures Using C++ 2E 41
Item Insertion using two pointers
• Using two pointers
• Can simplify insertion code somewhat
• The following statements insert newNode between p and q:
The last two statements can be switched
Data Structures Using C++ 2E 42
