DATA STRUCTURES
AND ALGORITHMS
CONTENTS
1. Basic concepts
2. Singly linked list
DATA STRUCTURES AND ALGORITHMS 3. Operations on linked list
7TH WEEK : LINKED LIST
3
OBJECTIVES CONTENTS
After this lesson, students can:
1. Basic concepts
1. Understand singly linked list data structure;
1.1. Pointer
2. Build two basic operations on singly linked list data structures:
1.2. Struct
Browse and Search
2. Singly linked list
3. Operations on linked list
3.1 Browse
3.2 Search
1. BASIC CONCEPTS 1. BASIC CONCEPTS
1.1. Pointer 1.1. Pointer
Pointer is a basic concept in the C programming Address in memory cell 0x13AB Address in memory cell 0x13AB
Pointer is a basic concept in the C programming
language, used to work with memory addresses. language, used to work with memory addresses.
0x56CD 0x56CD
A pointer variable is also a variable, which also needs The data type of the pointer is the data type of the
to be declared, initialized and used to store data. memory location to which it points.
Pointer Pointer
Pointer variables have their own addresses. The value of the pointer contains the memory address
A pointer variable does not store a value like a basic to which the pointer points.
Address in memory cell 0x56CD Address in memory cell 0x56CD
variable, it points to another address, which is an The address of the pointer is the address of the
address in RAM. 100 pointer variable itself in RAM. 100
Basic variable Basic variable
7 8
1. BASIC CONCEPTS 1. BASIC CONCEPTS
1.1. Pointer 1.1. Pointer
Address in memory cell 0x13AB
Declare: int *p; Example
• Declare a pointer to point to an integer 0x56CD
variable Print value: 22
• The value of p determines the address of the Pointer
variable Print out the same Print value : 22
memory address
Assign value: int a; int* p = &a; Address in memory cell 0x56CD
Print value : 11
• p points to variable a
100
Print value : 2
Basic variable
Source: [Link]
9 10
1. BASIC CONCEPTS 1. BASIC CONCEPTS
1.2. Struct 1.2. Struct
Struct is a data structure that is defined by the user (user defined datatype) A struct is a user-defined data type, consisting of a set of variables, which can have
different data types. typedef struct TNode{
A structure is a collection of variables, which can have different data types int a;
double b;
char* s;
}TNode;
typedef struct TNode{ TNode* q: q is a pointer that points to a variable of type TNode
int a; Qa: access to member a of the struct type
double b;
char* s; q = (TNode*)malloc(sizeof(TNode)): allocate memory for a TNode type
}TNode; and q points to the allocated memory area
11 12
CONTENTS 2. SINGLY LINKED LIST
2.1. Introduction
1. Basic concepts Singly linked list is an ordered list of elements; Elements are connected to each other
1.1. Pointer through a link.
Linked list and array:
1.2. Struct
2. Singly linked list Linked list Array
3. Operations on linked list Data structure type Don’t need to be the same Must be the same
Allocate memory Disperse Continuous, side by side
3.1 Browse
3.2 Search
13 14
2. SINGLY LINKED LIST CONTENTS
2.1. Introduction
Characteristic:
1. Basic concepts
• Each element of the list consists of two parts: Data and pointer, which stores the 1.1. Pointer
address of the next element in the list;
• In a singly linked list, each element only points to the next element;
1.2. Struct
• A linked list has a first element: that calls head; and a last element, the pointer part 2. Singly linked list
of the last element is always null.
3. Operations on linked list
3.1 Browse
head
5 9 3 ... 6 4 3.2 Search
15 16
3. OPERATIONS ON SINGLY LINKED LIST 3. OPERATIONS ON SINGLY LINKED LIST
3.1. Browse the list [Link] the list
Task: Visit each element of the list exactly once Task: Visit each element of the list exactly once
Idea: Use the next pointer to access the next element
head
5 9 3 ... 6 4
17 18
3. OPERATIONS ON SINGLY LINKED LIST 3. OPERATIONS ON SINGLY LINKED LIST
3.2. Search 3.1. Search
Task: Find the first element of the list whose value is equal to the input value Task: Find the first element of the list whose value is equal to the input value
Idea: Use the next pointer to access the next element
For example, find the first element of the list with value 3
head
5 9 3 ... 3 4
19 20
SUMMARY AND SUGGESTIONS CONTENTS
1. Summary:
1. Insert an element at the beginning of the list
The lesson introduced singly linked lists and two basic operations on singly linked lists:
browse and search 2. Insert an element at the end of the list
2. Suggestions: 3. Insert an element before an element in the list
Design and implement other operations on the list
21
OBJECTIVES CONTENTS
After this lesson, students can:
1. Insert an element at the beginning of the list
Understand the algorithm and successfully implement three basic operations
2. Insert an element at the end of the list
on singly linked lists: inserting an element at the beginning, end, and before an
element in a singly linked list. 3. Insert an element before an element in the list
24
1. INSERT AN ELEMENT AT THE BEGINNING OF THE LIST 1. INSERT AN ELEMENT AT THE BEGINNING OF THE LIST
1.1. Idea 1.2. Implement
head
Create new element
5 9 3 ... 6 4
If the current list is empty, returns
the new element
10
New element (1) Update head pointer to point
to the new element
Step 1: Create a new element (2) Update the next pointer of the
Step 2: Update head pointer to point to the new element new element: makes it points to
Step 3: Update the next pointer of the new element: makes it points to the the beginning of the old list,
beginning of the old list, thus the new element becomes the first thus the new element becomes
element of the list the first element of the list
25
CONTENTS 2. INSERT AN ELEMENT AT THE END OF THE LIST
2.1. Idea
1. Insert an element at the beginning of the list
head
2. Insert an element at the end of the list
3. Insert an element before an element in the list 5 9 3 ... 6 4
10
New element
Step 1: Create a new element
Step 2: Find the last element of the list
Step 3: Update the next pointer of the last element to point to the new
element
27 28
2. INSERT AN ELEMENT AT THE END OF THE LIST CONTENTS
2.2. Implement
1. Insert an element at the beginning of the list
Use a loop to find the last 2. Insert an element at the end of the list
element of a list
3. Insert an element before an element in the list
(1) Create new element
(2) Insert the new element after
the last element of the list
29 30
3. INSERT AN ELEMENT BEFORE AN ELEMENT OF THE LIST 3. INSERT AN ELEMENT BEFORE AN ELEMENT OF THE LIST
3.1. Idea 3.1. Implement
head
Find the element preceding a
X given node
5 9 3 ... 6 4
10
Insert anew element before the element X of the list: New element
Step 1: Create a new element
Step 2: Update the next pointer of the element before X as the new element Insertion
Step 3: Update the next pointer of new element as the X
31 32
SUMMARY AND SUGGESTIONS CONTENTS
1. Summary: 1. Delete an element of the list
Implement three operations to insert a new element into a singly linked list: insert an
2. Reverse the order of list elements
element at the beginning, at the end, and before an element of the list.
2. Suggestions:
Design and implement other operations on the list
33
OBJECTIVES CONTENTS
After this lesson, students can:
Understand the algorithm and successfully implement two basic operations on singly 1. Delete an element of the list
linked lists: 2. Reverse the order of list elements
• remove an element from the list
• reverse the order of elements in a list
36
1. DELETE AN ELEMENT OF THE LIST 1. DELETE AN ELEMENT OF THE LIST
1.1. Idea 1.2. Implement
If the list and element to be deleted
p are NULL, return head of the list
p
head
5 9 3 ... 6 4 If the element to be deleted is the
first element in the list, change the
first element and delete the element
that want to delete
• Check if the list and element to be deleted p are NULL?
• If the element to be deleted is at the beginning of the list Simple
• Use recursion to delete
Apply recursive technique for
deletion
37
CONTENTS 2. REVERSE THE ORDER OF THE LIST ELEMENTS
2.1. Problem
1. Delete an element of the list head
2. Reverse the order of list elements
Input: 5 9 3 ... 6 4
head
Output: 4 6 ... 3 9 5
39 40
2. REVERSE THE ORDER OF THE LIST ELEMENTS 2. REVERSE THE ORDER OF THE LIST ELEMENTS
2.2. Idea 2.3. Implement
Nguồn: [Link]
41 42
SUMMARY AND SUGGESTIONS
1. Summary:
Implement two important operations on singly linked lists: remove an element from
the list and reverse the order of the list's elements.
2. Suggestions: THANK YOU !
• A singly linked list has only 1 link between 2 consecutive elements in the list. If
there are 2 links, is it easier to operate on the list?
43 44