Chapter Four
Linked List
1
Types of Data Structures
There are two broad types of data
structure based on their memory
allocation:
Static data structure
Dynamic data structure
2
Static Data Structures
Are data structures that are defined &
allocated before execution, thus the
size cannot be changed during time of
execution.
Example:
Array implementation of ADTs.
3
Dynamic Data Structure
Are data structure that can grow and
shrink in size or permits discarding of
unwanted memory during execution
time.
Example:
Linked list implementation of ADTs.
4
Structure
Is a collection of data items and the data items
can be of different data type.
The data item of structure is called member of
the structure.
Declaration of structure
Structure is defined using the struct keyword.
struct name {
data type1 member 1;
data type2 member 2
.
.
data type n member n;
5
};
Example :
struct student {
char name[20];
int age;
char Dept[20];
};
The struct keyword creates a new user defined
data type that is used to declare variable of an
aggregated data type.
6
Accessing Members of Structure Variables
The Dot operator (.): to access data members
of structure variables.
The Arrow operator (->): to access data
members of pointer variables pointing to the
structure.
Example:
struct student stud;
struct student *studptr;
cout<<stud.name;
OR
cout<<studptr->name; 7
Self-Referential Structures
Structures can hold pointers to instances
of themselves.
Example:
struct student{
char name[20];
int age;
char Dept[20];
struct student *next;
};
8
Linked List
Is self-referential structure.
Is a collection of elements called nodes, each of
which stores two types of fields. Data items and
a pointer to next node.
The data field: holds the actual elements on the
list.
The pointer field: contains the address of the next
node in the list.
9
A linked list can be represented by a
diagram like this one: (Single linked list).
node
data pointer
A B C
Start
• Start (Head): Special pointer that points to
the first node of a linked list, so that we can
keep track of the linked list.
•The last node should points to NULL to show
that it is the last link in the chain (in the linked
10
list).
• This linked list has four nodes in it, each with
a link to the next node in the series (in the
linked list).
11
Variations of Linked Lists
Single linked lists: Discussed in the
previous two slides.
Circular linked lists:
▪ The last node points to the first node of the list.
A B C
Start
▪ How do we know when we have finished traversing the list? (Hint:
check if the pointer of the current node is equal to the Start (head)
pointer).
12
Doubly linked lists
• Each node points not only to Successor node (Next node), but
also to Predecessor node (Previous node).
• There are two NULL: at the first and last nodes in the linked
list.
• Advantage: given a node, it is easy to visit its predecessor
(previous) node. It is convenient to traverse linked lists
Forwards and Backwards.
A B C
13
Head (Start) Tail (End)
Operations of Linked List
Defining the data structure for linked lists
//Single linked list
struct student
{
char name[20];
int age;
char Dept[20];
student *next;
};
struct student *start = NULL;
14
Defining the data structure for
linked lists
//Double linked list
struct student
{
char name[20];
int age;
char Dept[20];
student *next;
student *prev;
};
struct student *start = NULL; 15
Adding a node to the list
Steps
1. Allocate a new node.
2. Set the node data values and make new
node point to NULL.
3. Make old last node’s next pointer point to
the new node.
4. *Make the new last node’s prev pointer
point to the old last node. (This is only for
Double Linked list).
16
Traversing through the list
To Move Forward:
Set a pointer to point to the same thing as the
start (head) pointer.
If the pointer points to NULL, display the
message “list is empty" and stop.
Otherwise, move to the next node by making
the pointer point to the same thing as the
next pointer of the node it is currently
indicating.
17
To Move Backward: (Single linked list)
1. Set a pointer to point to the same thing
as the start pointer.
2. If the pointer points to NULL, display the
message “list is empty" and stop.
3. Set a new pointer and assign the same
value as start pointer and move forward
until you find the node before the one
we are considering at the moment. 18
To Move Backward: (Double linked list)
1. Set a pointer to point to the same thing as the
end (tail) pointer.
2. If the pointer points to NULL, display the
message “list is empty" and stop.
3. Otherwise, move back to the previous node by
making the pointer point to the same thing as
the prev pointer of the node it is currently
indicating. 19
Display the content of list
Steps:
1. Set a temporary pointer to point to the same thing as
the start pointer.
2. If the pointer points to NULL, display the message
"End of list" and stop.
3. Otherwise, display the data values of the node
pointed to by the start pointer.
4. Make the temporary pointer point to the same thing
as the next pointer of the node it is currently
indicating.
5. Jump back to step 2. 20
Insert at the front (beginning)
1. Allocate a new
node.
2. Insert new element
values.
3. Make the next
pointer of the new
node point to old
head (start).
4. Update head (start)
to point to the new
node.
21
Inserting at the End
Steps
1. Allocate a new node.
2. Set the node data values and make the
next pointer of the new node point to
NULL.
3. Make old last node’s next pointer point to
the new node.
4. Update end to point to the new node.
22
Insertion in the middle
Steps:
Create a new Node
Set the node data Values
Break pointer connection
Re-connect the pointers
23
Exercise Single linked list
Write the function for add a new node
at the begging.
at the middle
at the end
Write a function that will be delete node
from the begging
from the end
from the middle by searching
Write the function of that displays the contents of each nodes.
Write a function search an element from the linked list.
Write a function to sort linked list elements by one of the
member of the node.
24
Quiz
Write the function for add a new node at
the begging.
Write a function that will be delete node
from the begging
25
