Содержание

Слайд 2

Data structures: List
List is a linear data structure:
Order is not given by

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

Algorithms and Data structures course

Слайд 3

Data structures: List Example

Algorithms and Data structures course

null

Here is the structure of list:
data

Data structures: List Example Algorithms and Data structures course null Here is
– 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.

Слайд 4

Data structures: List Structure

Algorithms and Data structures course

The following struct could be used

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

Слайд 5

Data structures: List Operations

insert: Inserts item to the specified position in list. Time

Data structures: List Operations insert: Inserts item to the specified position in
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

Слайд 6

Data structures: List Problems

For good understanding why insert and delete is O(1), let’s

Data structures: List Problems For good understanding why insert and delete is
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

Слайд 7

Data structures: List Problem: Cycle

You are given a list by its first node,

Data structures: List Problem: Cycle You are given a list by its
need to answer if there is a cycle in that list:
No cycle:
Has cycle:

Algorithms and Data structures course

nullptr

Слайд 8

Data structures: List Problem: Cycle

Here is visualization of mentioned algorithm:
First pointer is visualized

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

Algorithms and Data structures course

Слайд 9

Data structures: List Problem: Cycle

Here is visualization of mentioned algorithm:
First pointer is visualized

Data structures: List Problem: Cycle Here is visualization of mentioned algorithm: First
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

Слайд 10

Data structures: List Problem: Cycle

Here is visualization of mentioned algorithm:
First pointer is visualized

Data structures: List Problem: Cycle Here is visualization of mentioned algorithm: First
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

Слайд 11

Data structures: List Problem: Cycle

Here is visualization of mentioned algorithm:
First pointer is visualized

Data structures: List Problem: Cycle Here is visualization of mentioned algorithm: First
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

Слайд 12

Data structures: List Problem: Cycle

Here is visualization of mentioned algorithm:
First pointer is visualized

Data structures: List Problem: Cycle Here is visualization of mentioned algorithm: First
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

Слайд 13

Data structures: List Problem: Cycle

Here is visualization of mentioned algorithm:
First pointer is visualized

Data structures: List Problem: Cycle Here is visualization of mentioned algorithm: First
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

Слайд 14

Data structures: List Problem: Cycle

Here is visualization of mentioned algorithm:
First pointer is visualized

Data structures: List Problem: Cycle Here is visualization of mentioned algorithm: First
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

Имя файла: 007-List.pptx
Количество просмотров: 68
Количество скачиваний: 0