007 List

Data structures: List
List is a linear data structure:
Order is not given by their physical placement in memory.
Each element points to the next.
Example:
Train.
Algorithms and Data structures course

Data structures: List
Example
Algorithms and Data structures course
null
Here is the structure of list:
data – is a section for custom data, that list must hold.
pointer (grey part) – is a section that points to the next node. Last node points to the null.

Data structures: List
Structure
Algorithms and Data structures course
The following struct could be used to create a list from the last example:

Data structures: List
Operations
insert: Inserts item to the specified position in list. Time complexity is O(1).
remove: Removes item from the specified position in list. Time complexity is O(1).
access: Element accessing is performs by iteration to that element. Time complexity is O(n).
Algorithms and Data structures course

Data structures: List
Problems
For good understanding why insert and delete is O(1), let’s solve the following problems
Given a node, you need to insert given you value after this node.
Given a node, you need to delete the node located next to it.
Algorithms and Data structures course

Data structures: List
Problem: Cycle
You are given a list by its first node, need to answer if there is a cycle in that list:
No cycle:
Has cycle:
Algorithms and Data structures course
nullptr

Data structures: List
Problem: Cycle
Here is visualization of mentioned algorithm:
First pointer is visualized as blue node and second as green.
At the start both pointers points to the node 1
Algorithms and Data structures course

Data structures: List
Problem: Cycle
Here is visualization of mentioned algorithm:
First pointer is visualized as blue node and second as green.
On the step 1, first pointer start point to the node 2 and second to the node 3
Algorithms and Data structures course

Data structures: List
Problem: Cycle
Here is visualization of mentioned algorithm:
First pointer is visualized as blue node and second as green.
On the step 2, first pointer start point to the node 3 and second to the node 5
Algorithms and Data structures course

Data structures: List
Problem: Cycle
Here is visualization of mentioned algorithm:
First pointer is visualized as blue node and second as green.
On the step 3, first pointer start point to the node 4 and second to the node 7
Algorithms and Data structures course

Data structures: List
Problem: Cycle
Here is visualization of mentioned algorithm:
First pointer is visualized as blue node and second as green.
On the step 4, first pointer start point to the node 5 and second to the node 3
Algorithms and Data structures course

Data structures: List
Problem: Cycle
Here is visualization of mentioned algorithm:
First pointer is visualized as blue node and second as green.
On the step 5, first pointer start point to the node 6 and second to the node 5
Algorithms and Data structures course

Data structures: List
Problem: Cycle
Here is visualization of mentioned algorithm:
First pointer is visualized as blue node and second as green.
And on the step 6, both pointers will point on the same node 7, and algorithm will return true.
Algorithms and Data structures course