The Most Powerful Concepts in Programming Languages: Data Structure

In this blog, I would like to introduce the concepts that I believe are the most powerful in programming languages, and mastering them will give you solid programming thinking. I will explain them one by one with examples in Java and Python. After introducing the concepts of object orientation, recursion, concurrency, and functional programming in the earlier articles, I will elucidate the concept of data structure in this article.

1. Object-oriented
2. Recursion
3. Concurrency
4. Functional Programming and Lambda Expressions

5. Data Structure

6. Software Design Patterns
7. Annotations/Decorators
8. Machine Learning

1. Data Structure

A data structure is a way to save data to be processed by a program. A data structure allows the organization of data so that the program can access and manage it efficiently. Data structures provide built-in support for operations such as reading, inserting, deleting, and updating. Many types of data structures are defined in computer science to implement these operations in different ways to deal with various real-life situations based on criteria like the kind of required operations (insertion, deletion, update, and read), efficiency, and memory constraints. That’s why you should use a suitable data structure for each situation depending on the requirements of the problem at hand. Learn well the logic behind each data structure to use in the right context and take full advantage of its purpose. For clarity on this topic, we mention here some well-known data structures.

Array: It is a sequential collection of items saved in contiguous memory locations. You can access any element of the array using its index. In general, the length of an array is permanently fixed at the time of its initialization.

List: It is an ordered collection of elements. You can insert elements wherever you want. In other words, you can add one or many elements at the beginning, at the end, or after a specific element or position. You can access an element using its index or any other criteria (for example, identifier if your elements are objects). The size of the list is not fixed. A list can contain any number of elements.

Set: It’s an unordered data structure that implements the concept of the set as defined in mathematics. Each element in a set can only have one occurrence.

Queue: You typically use this data structure in situations where first come is always first served. Queues store data sequentially. You can add an item only to the end of the queue (enqueue) and remove only the first item from the queue (dequeue). Queues implement what we call the FIFO (First-In-First-Out) principle.

Stack: This data structure follows the Last-In-First-Out (LIFO) principle. That means that the last element added to the stack is the first that can be removed. In other words, you can only remove elements from the top. The main operations you can apply to a stack are ‘Push’, ‘Pop’, and ‘Top’ (sometimes called ‘Peek’). ‘Push’ consists of adding an element to the top of the stack. ‘Pop’ is used to remove the top element from the stack. The ‘Top’ operation consists of reading the top item of the stack without removing it. Stacks are essential for compilers to evaluate arithmetic expressions.

Key-Value Pairs: In key-value pair data structures, each key is associated with a single value. Keys are unique and allow values to be retrieved quickly. Hashing is a typical technique for implementing this type of data structure. The ‘Map’ data structure in Java is one of the implementations of key-value pairs. On the other hand, Python has the concept of ‘Dictionary’ which also implements the structure of key-value pairs.

2. Example in Java

Data structures are not only a way to store data but also a way to organize it and perform the necessary operations to implement your strategy to effectively solve a problem.

Let’s take an example of a queue in Java in this section. Queue is a data structure that follows the FIFO (First-In-First-Out) principle. That means that when you want to delete an item, it must be the first one you add to the queue. It reflects the principle of a queue, where a group of people wait in order of their arrival to buy a coffee at a coffeehouse. Programmatically, Java provides a ‘Queue’ interface that you can implement in different ways depending on your requirements.

However, it can also have consequences in terms of performance when executing some operations like reading, inserting, and deleting. Some implementations of the ‘Queue’ interface are ‘PriorityQueue’ and ‘LinkedList’. 

‘PriorityQueue’ implements a queue by keeping elements in a specific order, which can be natural order or custom order, such as alphabetical order of strings. You can use this implementation if you have requirements like storing tasks with priorities.

On the other hand, if you want to keep the same order in which you inserted your items, you can use ‘LinkedList’. This data structure contains elements in blocks linked to each other using pointers. The list has a link to the first element and each block (containing an element) stores the data and a link to the previous and next block in the list. ‘LinkedList’ allows you to perform efficient operations such as reading, updating, and deleting. Let’s take an example to show how to use ‘LinkedList’ to implement a queue:

import java.util.LinkedList;

import java.util.Queue;

public class LinkedListExample {

    public static void main(String[] args) {

        //Create a Queue using LinkedList

        Queue<String> queue = new LinkedList<>();

        //Add elements to the queue

        queue.add("E-1");queue.add("E-2");queue.add("E-3");

        //Display the content in the queue

        System.out.println("Queue: " + queue);

        //Show the first element of the queue

        System.out.println("First element: " + queue.peek());

        //Remove the first element from the queue

        System.out.println("Removed element: " + queue.poll());

        //Display the content of the queue after a deletion

        System.out.println("Queue after deletion: " + queue);

    }

}

In this example, we create a ‘queue’ instance by instantiating the ‘LinkedList’ class. We can add some elements to the queue using the ‘add’ method of the ‘LinkedList’. We can use the ‘peek’ method of the ‘LinkedList’ to display the elements in the queue and the ‘poll’ method to remove the first element from the front of the queue. The execution of the example above provides the following output:

Queue: [E-1, E-2, E-3]

First element: E-1

Removed element: E-1

Queue after deletion: [E-2, E-3]

3. Example in Python

Python offers many types of data structures that help you organize, store, and use your data efficiently. Find the best-suited data structure among those available to help you solve your problem. In other words, don’t take any type and struggle to adapt it to your specific use case. But choose the data structure that implements the necessary operations and fits your needs.

Now let’s introduce some of the most popular data structures in Python, namely lists and dictionaries.

3.1. Example 1: Lists

Lists are ordered and mutable collections of items of different types (integers, strings, ..). You can legitimately define a list like this:

mixed_list = [1, "Hello", None, -15.20]

Let’s take a simple example of a list called ‘int_list’ which contains elements of the same type (integer). The code below will be commented out and show some basic operations that can be applied to a list. These basic operations include accessing list elements using indexes and iterating over list elements. Other operations you can perform are adding, removing, or updating items from a list. You can add an item to the end of the list or add it to a specific index. You can also sort and reverse the list.

# Create a list of integers

int_list = [10, 25, -50, 27, 105]

print("Original list:", int_list)

# Access an element of the list using its index

# Get the first element

print("First element:", int_list[0])

# Get the second element

print("Second element:", int_list[1])

# Get the last element

print("Last element:", int_list[-1])

# Iterate over the elements of the list

print("Elements of the list:")

for num in int_list:

    print(" Element:", num)

# Iterate over the indexes of the list

print("Index-value of the list:")

for i in range(len(int_list)):

    print("  Element at index", i, "is", int_list[i])

# Sorting the list

int_list.sort()

print("Sorted list:", int_list)

# Reverse the list

int_list.reverse()

print("Reversed list:", int_list)

# Append an element to the end of the list: add here the number 280

int_list.append(280)

print("List after adding an element:", int_list)

# Update elements of the list: update here the third element

int_list[3] = 38

print("Updated list:", int_list)

# Insert an element at a specific position in the list: insert the number 35 at the index 2

int_list.insert(2, 35)

print("List after insertion:", int_list)

# Remove element from the list: remove here the element 25

int_list.remove(25)

print("List after removal:", int_list)

# Get the length of the list

print("Length of the list:", len(int_list))

# Check if an element exists in the list

if 15 in int_list:

    print("List contains the number 15")

else:

    print("List does not contain the number 15")

Running the code above gives us the following result:

Original list: [10, 25, -50, 27, 105]

First element: 10

Second element: 25

Last element: 105

Elements of the list:

 Element: 10

 Element: 25

 Element: -50

 Element: 27

 Element: 105

Index-value of the list:

  Element at index 0 is 10

  Element at index 1 is 25

  Element at index 2 is -50

  Element at index 3 is 27

  Element at index 4 is 105

Sorted list: [-50, 10, 25, 27, 105]

Reversed list: [105, 27, 25, 10, -50]

List after adding an element: [105, 27, 25, 10, -50, 280]

Updated list: [105, 27, 25, 38, -50, 280]

List after insertion: [105, 27, 35, 25, 38, -50, 280]

List after removal: [105, 27, 35, 38, -50, 280]

Length of the list: 6

List does not contain the number 15

3.1. Example 2: Dictionaries

Dictionaries are data structures made up of key-value pairs that enable efficient key-based search. They can contain values of different data types such as lists, nested dictionaries, or other objects.

Here we take a code example that shows how we apply certain operations to a dictionary named ‘employee’. These operations include accessing dictionary values using keys or extending the dictionary by adding new key-value pairs. 

You can also update dictionary values or delete keys from it. You can check whether a key exists in the dictionary or not. This is very useful because updating a value and deleting a key from the dictionary can result in an exception if the key does not exist. By checking the existence of the key, such exceptions can be avoided. You can certainly iterate through keys and values.

# Create a dictionary of employee

employee = {

    "firstname": "Mary",

    "age": 30,

    "position": "Junior Software Developer",

    "address": "Markt 100, Vienna Austria"

}

# Print the dictionary

print("Original dictionary:", employee)

# Access values in the dictionary using keys

print("First name:", employee["firstname"])

print("Age:", employee["age"])

print("Position:", employee["position"])

print("Address:", employee["address"])

# Update values in the dictionary

# Update the age

employee["age"] = 31

# Update the position

employee["position"] = "Senior Software Developer"

print("Updated dictionary:", employee)

# Add new key-value pairs to the dictionary

employee["lastname"] = "Smith"

# Add a value as a list to the key email

employee["email"] = ["mary@gmail.com", "marysmith@yahoo.com"]

# Nested dictionary

employee["task_priority"] = {"Task 1": 4, "Task 2": 3, "Task 3": 1}

print("Dictionary after adding new items:", employee)

# Remove key-value pairs from the dictionary:

# Remove the 'address' key

del employee["address"]

print("Dictionary after removing an item:", employee)

# Get the length of the dictionary

print("Length of the dictionary:", len(employee))

# Check if a key exists in the dictionary

if "lastname" in employee:

    print("Last name:", employee["lastname"])

else:

    print("Last name does not exist")

# Iterate over the key-value pairs of the dictionary and show them

print("Key-value pairs:")

for key, value in employee.items():

    print(key, ":", value)

# Get a list of keys and values from the dictionary

keys = list(employee.keys())

values = list(employee.values())

print("Keys:", keys)

print("Values:", values)

Executing the code above gives us the following output:

Original dictionary: {'firstname': 'Mary', 'age': 30, 'position': 'Junior Software Developer', 'address': 'Markt 100, Vienna Austria'}

First name: Mary

Age: 30

Position: Junior Software Developer

Address: Markt 100, Vienna Austria

Updated dictionary: {'firstname': 'Mary', 'age': 31, 'position': 'Senior Software Developer', 'address': 'Markt 100, Vienna Austria'}

Dictionary after adding new items: {'firstname': 'Mary', 'age': 31, 'position': 'Senior Software Developer', 'address': 'Markt 100, Vienna Austria', 'lastname': 'Smith', 'email': ['mary@gmail.com', 'marysmith@yahoo.com'], 'task_priority': {'Task 1': 4, 'Task 2': 3, 'Task 3': 1}}

Dictionary after removing an item: {'firstname': 'Mary', 'age': 31, 'position': 'Senior Software Developer', 'lastname': 'Smith', 'email': ['mary@gmail.com', 'marysmith@yahoo.com'], 'task_priority': {'Task 1': 4, 'Task 2': 3, 'Task 3': 1}}

Length of the dictionary: 6

Last name: Smith

Key-value pairs:

firstname : Mary

age : 31

position : Senior Software Developer

lastname : Smith

email : ['mary@gmail.com', 'marysmith@yahoo.com']

task_priority : {'Task 1': 4, 'Task 2': 3, 'Task 3': 1}

Keys: ['firstname', 'age', 'position', 'lastname', 'email', 'task_priority']

Values: ['Mary', 31, 'Senior Software Developer', 'Smith', ['mary@gmail.com', 'marysmith@yahoo.com'], {'Task 1': 4, 'Task 2': 3, 'Task 3': 1}]