Data Structures and Algorithms: For Laymen and Commonfolk — Part 1

You could not live with your own failure. Where did that bring you? Back to me

TLDR; “Perhaps you expect this to not be a lengthy read, then you are neither lay nor common”.

As much as a lot of folks have decided to treat coding like it’s a state function where only the initial and final states matter, well, it’s a sad delusion. Process is equally important when writing code, because it determines efficiency and quality. This sin oftentimes can be traced to the deliberate or indeliberate ignorance of the concept of data structures and algorithms, which is why we are here today. Therefore, this is an attempt to make saints out of sinners.

That said, perhaps you have spent most of your time as a software engineer writing code you know should not be alive and have decided to come clean and go straight, take a seat.

I will attempt to cover the concept from a high level and then drill down into lower levels but from very elementary points. Skip any aspect you find boring but keep it to yourself.

BRIEF HISTORY

The history of data structures and algorithms dates back to the early days of computer science, when researchers and programmers began developing methods for storing and manipulating data. The concept of a data structure refers to the way in which data is organized and stored in memory, while algorithms are the procedures and steps used to process and manipulate that data.

One of the earliest examples of data structures and algorithms can be traced back to the invention of the abacus, a manual device used for arithmetic calculations. The abacus is a form of a data structure that organizes data in the form of beads on rods, with each bead representing a value.

Let’s explore a more familiar example to bring home the concept to more practical levels.

PRACTICAL EXAMPLE OF DSA

Let’s consider a common example: a grocery list.

A grocery list is a data structure that allows us to organize the items we need to buy from a store. We can use various algorithms to perform tasks related to the grocery list, such as adding or removing items, sorting the list, and searching for specific items.

In this example, the grocery list is a simple data structure that can be represented as a list of items. Each item on the list is a piece of data that is associated with a specific index or position in the list. The list allows us to organize the data in a way that makes it easy to access and manipulate.

Algorithms are used to perform specific tasks related to the grocery list. For example, we can use an algorithm to add items to the list by appending them to the end of the list. We can also use an algorithm to remove items from the list by deleting them from the list or marking them as completed.

Sorting the list can be achieved using various algorithms, such as alphabetical sorting or sorting based on category.

Searching for specific items on the list can be done using an algorithm that iterates through the list and checks each item for a match.

DSA IN COMPUTER SCIENCE

Since the goal here is neither to remain lay forever, nor go shopping with more sophistication, let’s proceed to look at the concept in computer science.

Recall, a data structure is a way of organizing and storing data in a computer so that it can be accessed and used efficiently. An algorithm, on the other hand, is a step-by-step procedure for solving a problem or performing a task. Algorithms are used to manipulate data structures and can be used to perform various operations such as searching, sorting, and traversing

That said, there are various types of data structures, each with its own strengths and weaknesses. Some of the commonly used data structures are arrays, linked lists, stacks, queues, trees, and graphs.

DATA STRUCTURES

Arrays are the simplest and most commonly used data structure. They are a collection of elements of the same type, arranged in a contiguous block of memory. Arrays are efficient for accessing individual elements, but inserting or deleting elements from an array can be time-consuming, especially for large arrays.

Linked lists are a dynamic data structure that consists of a sequence of nodes, where each node contains a data element and a reference (pointer) to the next node in the sequence. Linked lists are efficient for inserting or deleting elements, but accessing individual elements can be slower than in an array.

Stacks are a data structure that follows the Last-In-First-Out (LIFO) principle. Elements are added and removed from the top of the stack. Stacks can be implemented using arrays or linked lists.

Queues are a data structure that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front. Queues can also be implemented using arrays or linked lists.

Trees are a hierarchical data structure that consists of nodes connected by edges. Each node has a parent node and zero or more child nodes. Trees are efficient for searching, insertion, and deletion of elements, and are commonly used in applications such as file systems and databases.

Graphs are a data structure that consists of vertices (nodes) connected by edges. Graphs can be directed (edges have a direction) or undirected (edges have no direction). Graphs are used in a variety of applications, such as social networks and road networks

ALGORITHMS

Algorithms are used to manipulate data structures and perform various operations. Here are some of the commonly used algorithms:

• Searching algorithms, such as linear search and binary search, are used to find an element in a data structure.
• Sorting algorithms, such as bubble sort, insertion sort, and quicksort, are used to arrange the elements of a data structure in a specific order.
• Traversal algorithms, such as depth-first search and breadth-first search, are used to visit all the nodes in a tree or graph.
• Greedy algorithms, such as the Kruskal’s algorithm and Dijkstra’s algorithm, are used to solve optimization problems.
• Dynamic programming algorithms, such as the Fibonacci sequence algorithm and the knapsack problem algorithm, are used to solve problems by breaking them down into smaller subproblems.

To bring this home, let us explore the concepts using a common language: Javascript (if you were thinking python, I’m not sorry I promise)

COMMON EXAMPLES IN JAVASCRIPT

Here are some common examples in JavaScript.

Data structures

1. Arrays: An array is a basic data structure in JavaScript that stores a collection of values, which can be of any data type. Arrays are indexed, meaning that each value is assigned a unique numerical index starting from 0. This allows for fast and efficient access to specific values in the array. But this couldn’t be the only advantage, could it?

Power of arrays

Example:

let numbers = [3, 5, 1, 9, 7];

// Accessing a value using index
console.log(numbers[2]); // Output: 1

// Iterating over an array
for(let i = 0; i < numbers.length; i++) {
  console.log(numbers[i]);
}

In the example above, we create an array of numbers and access a value using its index. We also iterate over the array using a for loop to print each value to the console. This is an example of the algorithm that we use to traverse the array.

2. Objects: Objects are another common data structure in JavaScript that store a collection of key-value pairs. Each key is a string that is used to access the corresponding value. Objects are used to represent complex data structures and can contain nested objects, arrays, and functions.

Example:

let person = {
  name: "John",
  age: 30,
  address: {
    street: "123 Main St",
    city: "New York",
    state: "NY"
  }
};

// Accessing values using keys
console.log(person.name); // Output: John
console.log(person.address.city); // Output: New York

In the example above, we create an object to store information about a person, including their name, age, and address. We access values using their keys, which is an example of an algorithm for accessing data in an object.

Algorithms

1. Sorting: Sorting is a common algorithm that is used to arrange elements in a specific order. There are many sorting algorithms, each with its own advantages and disadvantages. The most commonly used sorting algorithm in JavaScript is the built-in sort() method.

Example:

let fruits = ["banana", "apple", "orange", "grape"];

// Sorting an array using sort() method
fruits.sort();
console.log(fruits); // Output: ["apple", "banana", "grape", "orange"]

In the example above, we create an array of fruits and use the sort() method to sort the array in alphabetical order. This is an example of a sorting algorithm that is built into the JavaScript language.

2. Searching: Searching is another common algorithm that is used to find a specific value in a data structure. The most commonly used searching algorithm in JavaScript is linear search, which checks each element in the data structure until it finds the target value.

Example:

let numbers = [3, 5, 1, 9, 7];

// Linear search algorithm to find a value in an array
function linearSearch(arr, target) {
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === target) {
      return i;
    }
  }
  return -1;
}

console.log(linearSearch(numbers, 9)); // Output: 3

In the example above, we create an array of numbers and define a function to perform a linear search to find a specific value in the array. The function returns the index of the target value if it is found, or -1 if it is not found.

CONCLUSION

Now, perhaps you still feel lost and unsatisfied, and are certain this is not a broader reflection of other aspects of your life, well then, it’s okay to feel that way. I would recommend this course by Freecodecamp to aid you to grasp the concept better.

However, understanding data structures and algorithms would go a lot way to improve the performance and quality of the code you write.

One practical coding example where understanding data structures and algorithms can make a significant difference is when working with large datasets or performing complex operations on data. Let’s say you have an array of 10,000 numbers in JavaScript, and you need to find the largest number in the array.

Without an understanding of data structures and algorithms, one might simply use a basic loop to iterate through the array and compare each number to find the largest one. Here’s an example of what that might look like

let arr = [/* 10,000 numbers */];
let largest = arr[0];

for (let i = 1; i < arr.length; i++) {
  if (arr[i] > largest) {
    largest = arr[i];
  }
}

console.log(largest);

While this code will work, it's not very efficient. It requires iterating through the entire array, even if the largest number is found early on in the loop. With a larger dataset, this approach could become very slow and inefficient.

A better approach would be to use a more efficient algorithm, such as the divide and conquer algorithm for finding the maximum element in an array. Here's an example of what that might look like:

let arr = [/* 10,000 numbers */];

function findMax(arr, start, end) {
  if (start === end) {
    return arr[start];
  } else {
    let mid = Math.floor((start + end) / 2);
    let leftMax = findMax(arr, start, mid);
    let rightMax = findMax(arr, mid + 1, end);
    return Math.max(leftMax, rightMax);
  }
}

console.log(findMax(arr, 0, arr.length - 1));

This algorithm works by recursively dividing the array into smaller subarrays and finding the maximum element in each subarray. It then compares the maximum elements of the subarrays to find the overall maximum element. This approach is more efficient than a basic loop because it only needs to iterate through the array log₂(n) times, where n is the number of elements in the array.

The next set of articles will cover specific DSA patterns one ought to be familiar with.

If you like what you read, I’m happy you do. If you don’t, well, listen instead.