Data structures

Algorithmics – Session 3

  • What is a data structure?
  • Built-in data structures
  • Linked lists
  • Stacks
  • Queues
  • Recap of the session

What is a data structure?

Definitions

Data Struture

  • Way of organising data so that it can be processed more easily

Abstract data type

  • Data structures which are not built-in data types
  • An abstract data type is associated with operations to be performed on it

Why it is called abstract?

  • Because it does not specify how the data is represented nor how the operations are implemented

What is a data structure?

A few common abstract data types

  • Linked list – Elements are linked using pointers

    • Initialization, inserting/deleting, search, sort, etc.

  • Stack – Operations are performed in the LIFO (Last In First Out) order

    • Initialization, push, pop

  • Queue – Operations are performed in the FIFO (First In First Out) order

    • Initialization, push (enqueue), pop (dequeue)

  • Tree – Elements are arranged in a tree-like structure

    • Initialization, inserting/deleting, search, traverse, balance, etc.

  • Graph – Finite set of vertices and set of edges that connect a pair of nodes

    • Initialization, inserting/deleting (vertex, edge), search, partition, etc.

Built-in data structures

List: for ordered collections

  • Values are ordered from index 0 to size-1
  • Allows for duplicate values
  • It is mutable and dynamic
  • It allows for slice selection
# Define a list
my_structure = [1, 2, 3, 4, 5]
print(f"Initial list: {my_structure} with id {id(my_structure)}")

# Illustration of dynamic property
my_structure.append(6)

# Illustration of mutable property
my_structure[0] = 2
print(f"Modified list: {my_structure} still with id {id(my_structure)}")

# Illustration of slice selection
print(f"Two last elements: {my_structure[-2:]}")
Initial list: [1, 2, 3, 4, 5] with id 138495927307072
Modified list: [2, 2, 3, 4, 5, 6] still with id 138495927307072
Two last elements: [5, 6]

Built-in data structures

Set: for unordered collections

  • Does not allow for duplicate values
  • It is mutable and dynamic
# Define a set
my_structure = {1, 3, 5, 5}
print(f"Initial set: {my_structure} with id {id(my_structure)}")

# Add an element
my_structure.add(6)
print(f"Modified set: {my_structure} with id {id(my_structure)}")

# Test if an element belongs to the set
print(f"Contains 4: {4 in my_structure}")
Initial set: {1, 3, 5} with id 127760255235264
Modified set: {1, 3, 5, 6} with id 127760255235264
Contains 4: False

Built-in data structures

Tuple: for fixed collections

  • Values in a tuple are ordered
  • It allows for duplicate values
  • It is not mutable
# Initialize a tuple
my_structure = (1, "3", 3.14)
print(f"Initial tuple: {my_structure} with id {id(my_structure)}")
print(f"Second element: {my_structure[1]}")

# Extend the tuple into a new variable
my_structure += ("4",)
print(f"New tuple: {my_structure} with id {id(my_structure)}")
Initial tuple: (1, '3', 3.14) with id 132604205639104
Second element: 3
New tuple: (1, '3', 3.14, '4') with id 132604205672832

Built-in data structures

Dictionary: For indexed collections

  • It stores key/value pairs
  • It does not allow for key duplicate
  • It is mutable and dynamic
# Initialize a dictionary
my_dict = {'jack': 4098, 'sape': 4139}
print(f"Initial dict: {my_dict} with id {id(my_dict)}")

# Add a new entry and remove one
my_dict['guido'] = 4127
del my_dict['sape']
print(f"Modified dictionary: {my_dict} with id {id(my_dict)}")

# Check if an entry exists
print(f"Available entries: {list(my_dict)}")
print('guido' in my_dict)
Initial dict: {'jack': 4098, 'sape': 4139} with id 4408760320
Modified dictionary: {'jack': 4098, 'guido': 4127} with id 4408760320
Available entries: ['jack', 'guido']
True

Linked list

Definition and primitives

Linked list

  • A data struture consisting of nodes, each node having two elements, i.e., data and a reference to another node.

Doubly-linked list

  • A linked list where each stored value is linked to its preceding and succeeding values
  • Two entry pointers are provided: one to the head of the list and one to its tail
  • Primitives – Initialize, insert at beginning/end, pop from beginning/tail, check if empty

Stacks

Definition and primitives

  • A stack is a data structure in which the first element added is the last element removed
  • It is the LIFO (Last In, First Out) access strategy

  • The implementation details of the data are abstracted away
  • Primitives – Initialize, push, pop, check if empty

Queues

Definition and primitives

  • A queue is a data structure in which elements are removed in the order in which they are added
  • It is the FIFO (First In, First Out) access strategy

  • The implementation details of the data are abstracted away
  • Primitives – Initialize, enqueue, dequeue, check if empty

Recap of the session

What’s next?

Practical activity (~2h30)

Implementing algorithmic solutions with stacks and queues

  • Understanding diverse implementations of stacks and queues
  • Comparing different implementations
  • Do the optional activities if you have time

After the session

  • Review the articles of the session
  • Check your understanding with the quiz
  • Complete the practical activity
  • Check next session’s “Before the class” section