Data structure &
Programming II
Linked List data structure
A quick review
About the implementation of
linked list data structure
Lecture overview
❑ Overall lectures
1. Introduction to algorithm 7. Recursive
2. Basic data types and statements 8. File IO
9. Pointers
3. Control structures and Loop
10. Linked Lists
4. Array
11. Stacks and Queues
5. Data structure 12. Sorting algorithms
6. Sub-programs 13. Trees
C++
Outline
❑ A Brief of Outline
▪ What is linked list?
▪ Single linked list? Double linked list?
▪ What are the advantages of using linked list and array?
▪ Linked list implementation in C++
▪ Examples
Singly linked list Tail
What is Linked list? Head
NULL
❑ Definition
▪ A linked list is a data structure that can store an indefinite amount of elements (dynamic size)
▪ In a linked list, each element is linked with each other. struct Element
struct List
data: integer
Elements in a linked list are accessed sequentially. n: integer
*next: Element
*head: Element
▪ Each element contains End struct
*tail: Element
✓ Data End struct
✓ A link (pointer)
✓ to its next element (successor)
✓ and/or to its previous element (predecessor)
▪ Element = called a node
▪ In linked list, the first element is head and the last element is tail
Array Vs. Linked List
❑ Pros and Con
Array Linked List
▪ Fixed size ▪ Dynamically shrink and grow
▪ Once created, can’t add or reduce ▪ Dynamic memory management
number of elements to be stored ▪ No random access is allowed
▪ Can random access ▪ Slower access
▪ Faster access ▪ Elements not in contiguous memory locations
▪ Elements in contiguous memory locations
What is Linked list?
❑ Type of Linked List
▪ There are two types of linked lists:
▪ A single linked list is a linked list that has a link to either its successor or predecessor.
▪ A double linked list is a linked list that has both links to successor and predecessor.
Data
A pointer points to the next
TAIL
element (successor)
myList1
myList2 TAIL Last node of the list points to NULL
Remark
▪ A single or double linked list can be called a circular linked list when the last
element (tail) points to the first element (head).
Circular linked list
List Operations
❑ Operations with a list
✓Creating a list ✓Display data in list
✓Insert a new element to a list ✓Reverse a list
✓ Insert to beginning, end, at a position
✓Combine two lists
✓Delete an element from a list
✓ Delete to beginning, end, at a position
✓… etc.
✓Search an element in a list
✓Update an element in a list
Singly Linked List (SLL)
Singly linked list
❑ Overview
▪ An example of how a singly linked list is stored List
Element
Data
Address of next element
List operation
❑ Operation with a list
▪ All elements of a linked list can be accessed by
▪ First setup a pointer pointing to the first element (node) of the list
▪ Loop to traverse the list until NULL
▪ One of the disadvantage of the single linked list is
▪ Given a pointer A to a node, we can not reach any of the nodes that precede the node (previous
element) to which A is pointing
Operation on linked list
❑ Operations
Struct Element
data: data_type
*next: Element
End struct
Struct List ▪ n store number of elements in list.
*head: Element
▪ n is zero when list is first created.
*tail: Element
Then n is incremented by 1 when
n: Integer there is an element added to list.
End struct
Examples
❑ Create an element
Var *head, *tmp : Element
• Create an empty list
head null
• Add an element of the list with value 5 Reserve/allocate
memory for this element
tmp new(size(Element))
tmp→ data 5
tmp→ next null
head tmp
Examples
❑ Add and remove element
• Add a new element containing value 10 to the beginning of the list
tmp new(size(Element))
tmp→ data 10
tmp→ next head
head tmp
• Delete the first element from the list
tmp head
head head → next
free(tmp)
Create a list
❑ A function to create an empty list
Steps to create an empty list:
Function create_list( ) : Pointer of List
var *ls : List 1. Create a list variable
2. Allocate memory
ls new(size(List))
ls→n 0 3. Set 0 to n since we are creating an empty list
ls→head null 4. Head points to null
ls→tail null
5. Tail points to null
return ls
End function
Insertion
❑ Insert an element to the beginning of the list Old list
Procedure insert_be(*ls: List, d: data_type) Tail
var *E: Element
1 E new(size(Element))
E→data d
2
E→next ls→head
3 ls→head E
if(ls→n ==0) then Tail
4 ls→tail E Tail
end if
5 ls→n ls→n + 1
End procedure
Steps to add element to beginning of list
1. Create a new element E
2. Make next pointer of E points to head of list
3. Update E to be head of list Tail
4. Update tail if needed
5. Increase n by 1 (n is number of elements in list)
Display elements in list
Steps to display element in list
Procedure void(*ls: List) 1. Start from head
2. Move to each element each time
var *tmp: Element 3. …
tmp ls→head 4. …
while(tmp!=NULL) do
write(tmp→data)
tmp tmp→next
end while
End procedure
Implementation
Let’s take a look on another functions
▪ Add data to end of the list
▪ Search data in the list
▪ Delete data from begin of the list
Add data to the end of the linked list
❑ Let’s explore
▪ Create an element E
▪ Simply make the last element (tail) points to E.
▪ Finally, make E becomes tail.
Before
Tail
Head NULL
Head
NULL
1 2
Tail
The inserting element E After
Insert an element to the list Steps to add element to end of list
1. …
2. …
❑ Insert an element to end of the list 3.
4.
…
…
Procedure insert_end(*ls: List, d: data_type)
var *E: Element
if (ls→n == 0) then
insert_begin(ls, d)
else
E new(size(Element))
E→data d
E→next null
ls→tail→next E
ls→tail E
ls→n ls→n + 1
end if
End procedure
How it works … ?
How to search data in linked list
❖ Searching for data
Search
❑ Search for data in list
Tail
Head
NULL
Search
❑ Search for data in list
Steps to search element in list
1. …
2. …
3. …
4. …
We need to loop through the
list. Test condition for the
search.
How it works … ?
How to delete data from linked list
❖ Delete first element
(delete from beginning)
Deletion
❑ Delete the first element
Tail
Before
Head
NULL
NULL
Head
After
Delete the first element (delete beginning)
Head Tail
Head
tmp
NULL
tmp
How it works … ?
Q&A
More about delete
▪ Delete last element
▪ Delete all elements in the list
How to delete data from linked list
❖ Delete last element
(delete from end)
Deletion
❑ Delete the last element from single linked list
Tail NULL tmp
Head
NULL
Before
Tail
Head
NULL
After NULL
Delete the last element
Procedure delete_last(*ls: List)
var *tmp: Element 2
var i: integer Tail 5
Tail
if(ls→n==1) then
delete_be(li) Head
else 1 NULL
//Go to the 2nd last element
tmp ls→head
4
for(i1; <= ls→n - 2; i++) do tmp 3
tmp tmp→next 1 NULL
end for tmp
2 //update tail and delete last old element
ls→tail tmp
3
tmp tmp→next
ls→tail→next NULL 4
5 free(tmp)
ls→n ls→n - 1
end
End procedures
Delete first element
How it works … ?
(delete beginning)
How to delete data from linked list
❖ Delete all data
(destroy list)
Destroy a list
❑ Delete all data in list
Procedure destroy_list(*ls: List)
while(ls→n > 0) do
delete_be(ls)
end while
End procedure
How it works … ?
