---
marp: true
theme: kurzus
paginate: true
footer: Data Structures · Week 1 · Introduction, elementary data types
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# Data Structures

## Week 1 – Introduction, data and elementary data types

Dr. Ferenc Koczka · Eszterházy Károly University · 2026

---

## About the lecturer

- **Dr. Ferenc Koczka**, Assistant Professor
- Eszterházy Károly University, Eger, Hungary
- E-mail: **koczka.ferenc@uni-eszterhazy.hu**
- Consultation: after the classes, or by appointment via e-mail

> “First, solve the problem. Then, write the code.” – John Johnson

<!--
Time plan (lecture, 90 min): introduction 10' · algorithms 15' · data types 35' · data structures 30'.
-->

---

<!-- _class: kicsi -->

## Course outline

| Week | Topic | Week | Topic |
|---|---|---|---|
| 1 | Introduction, elementary data types | 9 | Dynamic memory, linked list |
| 2 | Efficiency, searching | 10 | Sentinel, doubly linked and circular lists |
| 3 | Arrays | 11 | Dynamic stack and queue, hash table |
| 4 | Strings | 12 | Recursion |
| 5 | Sorting I (simple sorts) | 13 | Sorting II (merge sort, quicksort) |
| 6 | Set | 14 | Trees, binary trees, traversals |
| 7 | Stack | 15 | Binary search tree, heap, summary |
| 8 | Queue | 16 | **Final test and practical exam** |

Every week: **2 hours of lecture + 2 hours of practice** (Java and Go)

---

## Requirements and tools

<div class="ket-hasab">
<div>

### Assessment (week 16)

- **Final test** (theory, 90 minutes)
  true/false, multiple choice, code tracing, pseudocode
- **Practical exam** (on a computer)
  implementing a data structure in Java **or** Go

</div>
<div>

### Tools

- **Java** – JDK 17 or newer
- **Go** – 1.23 or newer
- Editor: VS Code, IntelliJ IDEA or Eclipse
- Example programs: `code/java/wXX`, `code/go/wXX`

</div>
</div>

---

## Why do we study data structures?

> **Algorithms + Data Structures = Programs**
> – Niklaus Wirth (1976)

- The same task is fast with a **good** data structure and unusably slow with a **bad** one
- Every programming language builds on these foundations (`ArrayList`, `HashMap`, Go `slice`, `map` …)
- A favourite topic of job interviews
- Later courses (databases, operating systems, artificial intelligence) assume this knowledge

<div class="doboz tipp">

**Goal:** know the fundamental data structures, their operations and their efficiency – and be able to **implement** them.

</div>

---

<!-- _class: fejezet -->

# Problem solving and algorithms

---

## The steps of problem solving

![w:1100](kepek/h01_lepesek.svg)

- **Specification:** what is the input, what is the output, which conditions must hold?
- **Data structure + algorithm:** how do we store the data, and in which steps do we process it?
- This course is about the middle step

---

## The concept of an algorithm

**Algorithm:** a procedure consisting of a finite number of well-defined steps that solves a problem.

Its properties:

- **Finite** – it stops after a finite number of steps
- **Definite (deterministic)** – every step is precisely defined
- **Has input** – zero or more data items
- **Has output** – at least one result
- **Effective** – every step can actually be carried out
- **General** – it solves a whole class of problems, not just one case

---

## Ways to describe algorithms

| Tool | Advantage | Disadvantage |
|---|---|---|
| Plain text | everybody understands it | imprecise, long |
| Flowchart | visual | unreadable for large problems |
| **Pseudocode** | precise, language-independent | the notation must be learned |
| Program code | executable | language-specific details |

In this course: **pseudocode** in the lectures and in the test, **Java and Go** in the practice classes.

---

<!-- _class: kicsi -->

## Pseudocode notation

| Notation | Meaning |
|---|---|
| `x ← expression` | assignment |
| `If condition then … else … End if` | selection |
| `While condition … End while` | pre-test loop |
| `For i ← 1 to n … End for` | counting loop |
| `Function Name(parameters) … Return value … End function` | function |
| `Procedure Name(parameters) … End procedure` | procedure (no return value) |
| `A[i]` | the *i*-th element of an array – **indexing starts at 1** |
| `and`, `or`, `not` · `div`, `mod` | logical operators · integer division, remainder |

<div class="doboz figyelem">

In Java and Go, array indexing starts at **0** – always keep this in mind when writing code!

</div>

---

<!-- _class: kicsi -->

## Example: greatest common divisor (Euclid)

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">Pseudocode</span>

```text
Function GCD(a, b)
  While b ≠ 0
    m ← a mod b
    a ← b
    b ← m
  End while
  Return a
End function
```

| a | b | a mod b |
|---|---|---|
| 1071 | 462 | 147 |
| 462 | 147 | 21 |
| 147 | 21 | 0 |
| **21** | 0 | |

</div>
<div>

<span class="cimke java">Java</span>

```java
static int gcd(int a, int b) {
    while (b != 0) {
        int m = a % b;
        a = b;
        b = m;
    }
    return a;
}
```

<span class="cimke go">Go</span>

```go
func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
```

</div>
</div>

<!-- Code: code/java/w01/Gcd.java, code/go/w01/gcd -->

---

<!-- _class: fejezet -->

# Data and data types

---

## Data and information

- **Data:** a recorded, processable form of some property of reality
  e.g. `37.2`, `"Wuhan"`, `true`
- **Information:** the meaning of the data in a given context
  e.g. “the patient's body temperature is 37.2 °C”
- The computer works with **data** – the meaning is given by the program (and the programmer)

### Properties of a data item

- **Name** (identifier) – how we refer to it: `temperature`
- **Type** – which values it can take, and what we can do with it
- **Value** – its current content
- **Address** – where it is located in memory

---

## The data type

A **data type** defines three things:

1. **Set of values** – which values it can take
2. **Operations** – what we can do with the values
3. **Representation** – how the machine stores it (how many bits, which encoding)

<div class="doboz">

**Example – `int` (Java):**
values: −2 147 483 648 … 2 147 483 647 · operations: `+ − * / % == < …` · representation: 32 bits, two's complement

</div>

### Classification

- **Elementary (simple) type:** cannot be divided further – boolean, character, integer, real, pointer
- **Composite type (data structure):** built from elementary data – array, record, list …

---

<!-- _class: kicsi -->

## Elementary types in Java and Go

| Kind | Java | Go | Size |
|---|---|---|---|
| boolean | `boolean` | `bool` | – |
| character | `char` (UTF-16 code unit) | `rune` (= `int32`, Unicode code point) | 16 / 32 bits |
| byte | `byte` (signed) | `byte` (= `uint8`, unsigned) | 8 bits |
| integer | `short`, `int`, `long` | `int8`, `int16`, `int32`, `int64`, `int` | 16 / 32 / 64 bits |
| unsigned integer | – | `uint8` … `uint64`, `uint` | 8 … 64 bits |
| real | `float`, `double` | `float32`, `float64` | 32 / 64 bits |
| pointer / reference | reference (to objects) | `*T` pointer | 64 bits |

<div class="doboz tipp">

In Go the size of `int` depends on the machine (almost always 64 bits today); in Java `int` is always 32 bits.

</div>

---

## Representing integers

![w:820](kepek/h01_bitek.svg)

- With *n* bits, **2ⁿ** different values can be represented
- Signed integer (two's complement): **−2ⁿ⁻¹ … 2ⁿ⁻¹ − 1**
- Java `int` (32 bits): −2 147 483 648 … 2 147 483 647

---

## Overflow

If the result of an operation does not fit into the type, the value **“wraps around”** – without any error message!

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
int max = Integer.MAX_VALUE;
System.out.println(max + 1);
// -2147483648

byte b = 127;
b++;              // -128
```

</div>
<div>

<span class="cimke go">Go</span>

```go
var max int32 = math.MaxInt32
max++
fmt.Println(max)
// -2147483648

var b int8 = 127
b++               // -128
```

</div>
</div>

<div class="doboz figyelem">

Always choose a type in which even the largest expected value fits (e.g. `long` / `int64`).

</div>

---

## Real numbers: floating-point representation

- Form: **sign × mantissa × 2^exponent** (IEEE 754 standard)
- `float` / `float32`: about 7 significant digits · `double` / `float64`: about 15–16 significant digits
- Most decimal fractions (e.g. 0.1) **cannot be represented exactly** in binary

<div class="ket-hasab">
<div>

```java
double s = 0.1 + 0.2;
System.out.println(s);
// 0.30000000000000004
System.out.println(s == 0.3); // false
```

</div>
<div>

**Solution:** compare with a tolerance

```java
final double EPS = 1e-9;
Math.abs(s - 0.3) < EPS   // true
```

</div>
</div>

<div class="doboz tipp">

For financial calculations we use integers (e.g. fen, cents) or the `BigDecimal` type.

</div>

---

## Integer division and type conversion

- The quotient of two integers is an **integer**: `7 / 2 == 3`, the remainder: `7 % 2 == 1`
- If at least one operand is real, the result is real: `7 / 2.0 == 3.5`

```java
double f = 9 / 5 * celsius + 32;     // WRONG: 9 / 5 == 1
double f = 9.0 / 5 * celsius + 32;   // correct
```

**Conversion (type casting):**

- **Widening** (`int` → `long`, `int` → `double`): safe, automatic in Java
- **Narrowing** (`double` → `int`, `int` → `byte`): data may be lost, only when explicitly requested
  `(int) 3.99 == 3` (truncates) · `(byte) 300 == 44` (only the lowest 8 bits remain)
- In Go **every** conversion must be written out: `float64(a) / float64(b)`

---

## Characters: ASCII and Unicode

- **ASCII:** 7 bits, 128 characters (English alphabet, digits, punctuation)
  `'A' = 65`, `'a' = 97`, `'0' = 48` → `'a' - 'A' == 32`
- **Unicode:** all writing systems of the world, > 150 000 characters
  `'中' = U+4E2D = 20013` · `'é' = U+00E9 = 233`
- **UTF-8:** variable-length encoding (1–4 bytes) – the default on the web and in Go

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
char c = 'A';
System.out.println((int) c);   // 65
char d = (char) (c + 1);        // 'B'
```

</div>
<div>

<span class="cimke go">Go</span>

```go
c := 'A'               // rune
fmt.Println(c)         // 65
fmt.Printf("%c", '中') // 中
```

</div>
</div>

Strings are covered in detail in **week 4**.

---

## The boolean type and logical operations

<div class="ket-hasab">
<div>

| a | b | a **and** b | a **or** b | **not** a |
|---|---|---|---|---|
| F | F | F | F | T |
| F | T | F | T | T |
| T | F | F | T | F |
| T | T | T | T | F |

</div>
<div>

| Operation | Java | Go |
|---|---|---|
| and | `&&` | `&&` |
| or | `\|\|` | `\|\|` |
| not | `!` | `!` |
| exclusive or | `^` | `!=` |

</div>
</div>

- **Short-circuit evaluation:** in `a && b`, if `a` is false, `b` is not evaluated at all
  `if (i < n && t[i] > 0)` – never indexes past the end of the array!

---

## Literals, variables, constants

- **Literal:** a value written directly into the program text
  `42`, `0x2A`, `0b101010`, `3.14`, `2.5e3`, `'A'`, `"hello"`, `true`
- **Variable:** a named storage location whose value can change while the program runs
- **Constant:** a named value that **cannot change**

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
int count = 0;              // variable
final int DAYS = 7;         // constant
long big = 9_000_000_000L;  // L: long
float f = 2.5f;             // f: float
```

</div>
<div>

<span class="cimke go">Go</span>

```go
var count int      // 0 is the zero value
n := 10            // short declaration
const Days = 7     // constant
var f float32 = 2.5
```

</div>
</div>

---

## Pointers and references

![w:1050](kepek/h01_ertek_referencia.svg)

- **Pointer:** a data item whose value is a **memory address**
- With a pointer we access another data item indirectly
- Special value: **null / nil** – “points nowhere”

---

<!-- _class: kicsi -->

## References in Java, pointers in Go

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

- Primitive type (`int`, `double` …): the variable stores **the value**
- Object (array, `String`, own class): the variable stores a **reference**
- No pointer arithmetic, the address is not visible

```java
int[] a = {10, 20, 30};
int[] b = a;      // the same array!
b[0] = 99;
System.out.println(a[0]);  // 99
```

</div>
<div>

<span class="cimke go">Go</span>

- Every type is copied by value – even an array (`[3]int`)
- Pointer: `&x` is the address, `*p` is the value pointed to
- A slice (`[]int`) and a `map` contain a reference internally

```go
x := 5
p := &x        // p stores the address
*p = 6
fmt.Println(x) // 6
```

</div>
</div>

<div class="doboz">

Pointers/references make **dynamic data structures** possible (linked list, tree) – see from week 9.

</div>

---

<!-- _class: fejezet -->

# Data structures

---

## What is a data structure?

A **data structure** is a collection of logically related data elements, defined by

1. its **elements** (and their types),
2. the **relationships** between the elements,
3. the **operations** that can be performed.

<div class="doboz">

**Example – a class list:** elements: names (strings) · relationship: alphabetical order (everybody has a predecessor and a successor) · operations: search, insert a new name, delete a name

</div>

Data structures are classified according to several criteria ▶

---

## Classification: type and number of elements

### By the type of elements

- **Homogeneous:** all elements have the same type – array, string, set
- **Heterogeneous:** the elements may have different types – record (`class` / `struct`)

### By the number of elements

- **Static:** the number of elements is fixed at creation and does not change later
  Java array `new int[10]`, Go array `[10]int`
- **Dynamic:** the number of elements can change at run time
  linked list, `ArrayList`, Go `slice`, tree

---

## Classification: way of storage

![w:1050](kepek/h01_tarolas.svg)

- **Contiguous:** the address of the *i*-th element can be computed: `base address + (i − 1) · element size`
- **Scattered:** each element stores the location of the next one (pointer) – no shifting needed when inserting

---

## Classification: access to the elements

- **Direct (random) access:** every element can be reached in the same time, by index
  array: `t[1000]` is as fast as `t[0]`
- **Sequential access:** an element can only be reached by passing through the ones before it
  linked list, (magnetic tape)
- **Associative (content-based) access:** an element is reached by a key
  hash table: `map["Wuhan"]`
- **Restricted access:** only a specific element is accessible
  stack (only the top), queue (only the front)

---

## Classification: relationships between elements

![w:1100](kepek/h01_osztalyozas.svg)

---

<!-- _class: kicsi -->

## Overview: the data structures of the course

| Data structure | Elements | Size | Storage | Access | Relationship | Week |
|---|---|---|---|---|---|---|
| array | homogeneous | static | contiguous | direct | linear | 3 |
| string | homogeneous | static* | contiguous | direct | linear | 4 |
| set | homogeneous | variable | several | – | none | 6 |
| stack, queue | homogeneous | dynamic | contiguous or scattered | restricted | linear | 7, 8, 11 |
| linked list | homogeneous | dynamic | scattered | sequential | linear | 9, 10 |
| hash table | homogeneous | dynamic | mixed | associative | none | 11 |
| binary tree | homogeneous | dynamic | scattered (or array) | sequential | hierarchical | 14, 15 |
| record | heterogeneous | static | contiguous | direct (field name) | – | – |

<span class="halvany">* In Java and Go strings are immutable.</span>

---

## Operations on data structures

| Operation | Meaning |
|---|---|
| **Creation** | producing an empty structure |
| **Insertion** | adding a new element |
| **Deletion** | removing an element |
| **Modification** | changing the value of an element |
| **Search** | finding an element with a given property |
| **Traversal (processing)** | visiting every element once |
| **Sorting** | putting the elements in order |

A data structure is good for a task if its **most frequent operations are fast**.

---

## Abstract data type (ADT)

- **ADT:** a data structure defined by its **operations** – *what* it can do, not *how*
- The implementation (representation) can be hidden and replaced

<div class="ket-hasab">
<div>

<span class="cimke java">Java – interface</span>

```java
interface Stack {
    void push(int x);
    int pop();
    boolean isEmpty();
}
```

</div>
<div>

<span class="cimke go">Go – interface</span>

```go
type Stack interface {
    Push(x int)
    Pop() int
    IsEmpty() bool
}
```

</div>
</div>

The same stack can be implemented with an **array** (week 7) or a **linked list** (week 11) – the user's code does not change.

---

## Summary

- Programs = **algorithms + data structures**
- An algorithm is a finite, well-defined sequence of steps; we describe it in **pseudocode** (indexing from 1)
- A **data type** = set of values + operations + representation
- Representations have limits: **overflow**, **floating-point inaccuracy**, **integer division**
- A **pointer/reference** stores a memory address
- Classification of data structures: homogeneous/heterogeneous · static/dynamic · contiguous/scattered · direct/sequential access · linear/hierarchical/network

**Next week:** How do we measure the efficiency of an algorithm? Linear and binary search.

---

## Review questions

True or false?

1. An array is a heterogeneous data structure.
2. The elements of a linked list are accessed sequentially.
3. In Java, `Integer.MAX_VALUE + 1` causes a run-time error.
4. In Java, the value of the expression `0.1 + 0.2 == 0.3` is false.
5. The value of a pointer is a memory address.
6. The values of the elements of a static data structure cannot change.

<!--
Answers: 1. F (homogeneous)  2. T  3. F (wraps around, -2147483648)  4. T  5. T
6. F – "static" refers to the NUMBER of elements; the values can be modified.
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# Practice

---

<!-- _class: gyak -->

## Setting up the environment

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```bash
java -version          # 17 or newer
cd code/java/w01
java Types.java        # compile + run
```

or the classic way:

```bash
javac Types.java
java Types
```

</div>
<div>

<span class="cimke go">Go</span>

```bash
go version             # 1.23 or newer
cd code/go
go run ./w01/types
```

Formatting and checking:

```bash
gofmt -w .
go vet ./...
```

</div>
</div>

---

<!-- _class: gyak -->

## Demo programs

| Program | Java | Go | What does it show? |
|---|---|---|---|
| Elementary types | `Types.java` | `w01/types` | ranges, literals, character codes, constants |
| Pitfalls | `Pitfalls.java` | `w01/pitfalls` | overflow, integer division, 0.1 + 0.2, conversion |
| Value and reference | `ValueRef.java` | `w01/valueref` | parameter passing, aliasing, null/nil, swap |
| Euclid | `Gcd.java` | `w01/gcd` | pseudocode → code, printing the steps |

<div class="doboz tipp">

Run each of them, and **before** running, guess what it will print! We will discuss the surprising lines.

</div>

<!--
Go-specific note: in Go, 0.1 + 0.2 as a CONSTANT expression is exactly 0.3 (the compiler computes with arbitrary precision),
so the pitfalls program uses variables to show the inaccuracy.
-->

---

<!-- _class: gyak -->

## Exercises

1. **Number of bits:** write a function that returns how many bits are needed to store an integer *n* ≥ 0! (`255 → 8`, `256 → 9`)
2. **Binary form:** print the binary form of a positive integer by repeated division by 2! (`50 → 110010`)
3. **Upper case:** convert a lower-case letter to upper case using its character code (without library functions)!
4. **Comparing reals:** write an `almostEqual(x, y)` function with a tolerance!
5. **Truth table:** print the truth tables of `and`, `or`, `not` and `exclusive or`!
6. **Overflow check:** decide **before adding** whether `x + y` would overflow (`int` / `int32`)!

Solutions: `Exercises01.java`, `w01/exercises`

---

<!-- _class: gyak -->

## Homework

1. What is the value of `(byte) 200` in Java, and of `int8(200)` in Go? Compute it by hand, then check it!
2. How many different values can a 16-bit unsigned integer store? What is its largest value?
3. Write a program that prints every character of the text `"Hello, 世界"` together with its Unicode code!
4. Find everyday examples of a **stack**, a **queue** and a **tree** structure!

<!--
Answers: 1. 200 = 1100 1000 → -56.  2. 65 536 values, the largest is 65 535.
3. Java: for (char c : s.toCharArray()) ... (fine within the BMP); Go: for _, r := range s { fmt.Printf("%c %d\n", r, r) }
4. stack: plates, the browser "back" button; queue: canteen queue, print queue; tree: folder structure, family tree, organisation chart.
-->