We just posted a 49-hour course on the freeCodeCamp.org YouTube channel that will teach you everything you need to know about data structures and algorithms. Parth Vyas created this course.

Technical interviews often hinge on your ability to confidently solve problems using data structures and algorithms (DSA), which can feel challenging without the right foundation. In this comprehensive course, Parth will strip away the intimidation and equip you with the essential knowledge, starting with the core concepts of data structures, algorithms, and fundamental analysis like time and space complexity.

You'll learn how to judge an algorithm's efficiency using Big O notation and apply this important skill to code blocks. The course covers almost every major data structure and algorithm pattern, from Arrays, Linked Lists, Stacks, and Queues to advanced topics like Trees, Graphs, Dynamic Programming, and Backtracking.

Here are the sections in this course:

• Technical interviews 101

• How to judge an algorithm

• What is time complexity

• What is Big O

• Big O for code blocks

• Space complexity example

• How do you get good at solving DSA problems

• Types of data structures

• Quick recap

• Arrays

• Sliding window

• Two pointers

• Strings

• Sorting & searching

• Linked list

• Stack

• Queue

• Priority queue

• Trees

• Graph

• Dynamic programming

• Greedy

• Interval

• Backtracking

• Math & geometry

• Matrix

• Design

• Bit manipulation

Watch the full course on the freeCodeCamp.org YouTube channel (49-hour watch).

The three fundamental building blocks you’ll use every day are:

• Arrays: fixed-size sequences of elements.

• Slices: flexible, dynamic views of arrays.

• Maps: key–value stores implemented as hash tables.

With these three, you can represent almost any collection of data you need.

In this tutorial, you'll learn how to use arrays, slices, and maps effectively. You'll also peek under the hood to see how Go represents them in memory. This will help you understand their performance characteristics and avoid common pitfalls.

By the end, you'll be able to:

• Choose the right data type for your problem.

• Write idiomatic Go code for collections.

• Understand how these types behave internally.

• Build a small project combining arrays, slices, and maps.

Let's dive in!

What We’ll Cover:

1. Prerequisites

2. Arrays in Go

   • Initializing with Values

   • Array Length

   • Inner Representation of Arrays

   • Multi-dimensional Arrays

   • Limitations

   • When Arrays Are Useful

3. Slices in Go

   • When to use slices?

   • How to Declare a Slice

   • Allocate (with make)

   • Append Elements

   • How to Slice Slices

   • Inner Representation of Slices

   • How to Copy Slices

   • Multi-dimensional Slices

   • Slices vs Arrays

4. Maps in Go

   • How to Declare a Map

   • How to Access Values

   • How to Iterate Over a Map

   • Inner Representation of Maps

   • Arrays vs. Slices vs. Maps

5. Mini Project: Shopping Cart Totals

6. Practice Challenge

7. Conclusion

   • Practice Challenge Solution

Prerequisites

This tutorial is designed for readers who already have some basic experience with Go. You don’t need to be an expert, but you should be comfortable with:

• Writing and running simple Go programs (go run, go build).

• Declaring and using variables, functions, and basic types (for example, int, string, bool).

• Understanding control structures like if, for, and range.

• Using the Go toolchain and go mod init to set up a project.

If you’ve completed the Tour of Go or written a few small Go programs, you’ll be ready to follow along – we’ll cover the internals at a beginner-friendly level.

Arrays in Go

An array is a numbered sequence of elements of the same type with a fixed length. Here’s an example in Go:

package main

import "fmt"

func main() {
    var nums [3]int // array of 3 integers
    fmt.Println(nums) // [0 0 0]
}

This code declares an array with space for exactly three int values. Go arrays are zero-indexed, meaning the first element is at index 0. The elements, like every Go variable, are initialized to the zero value of their type (0 for integers, ““ for strings, and so on).

Once the array is created, you can access its elements using their index like this:

package main

import "fmt"

func main() {
    var nums [3]int // array of 3 integers
    nums[1] = 2
    fmt.Println(nums[1]) // 2
    fmt.Println(nums) // [0 2 0]
}

Initializing with Values

So far, we’ve seen that arrays are created with their elements set to the zero value of the element type. But often, you’ll want to give an array specific starting values right when you declare it. This process is called initialization: you provide the values in a list, and Go fills the array in order.

package main

import "fmt"

func main() {
    nums := [3]int{1, 2, 3} // array of 3 integers
    fmt.Println(nums) // [1 2 3]
}

If you omit the size when initializing an array, Go will infer it from the number of elements you provide:

package main

import "fmt"

func main() {
    nums := [...]int{1, 2, 3} // array of 3 integers
    fmt.Println(nums) // [1 2 3]
}

If you specify the size explicitly, the compiler will enforce that size:

package main

import "fmt"

func main() {
    nums := [3]int{1, 2} // array of 3 integers
    fmt.Println(nums) // [1 2 0]
}

Array Length

In Go, the length of an array is part of its type. [3]int and [4]int are considered completely different types, even though they both hold integers (you cannot assign a [4]int to a [3]int, or even compare them directly, because their lengths don’t match):

package main

import "fmt"

func main() {
    var a [3]int
    var b [4]int
    fmt.Println(a == b) // compilation error
}

When you use [...] in an array literal, Go counts how many elements you’ve provided and that will be the length. The length of an array is fixed and cannot be changed afterwards.

You can retrieve the length of an array using the built-in len function:

package main

import "fmt"

func main() {
    nums := [3]int{1, 2, 3}
    fmt.Println(len(nums)) // 3
}

Inner Representation of Arrays

In Go, arrays are represented as contiguous blocks of memory. This means that the elements of an array are stored one after the other in memory, making it easy to calculate the address of any element based on its index.

For example, consider the following array:

package main

import "fmt"

func main() {
    nums := [3]int32{1, 2, 3} // array of 3 32-bit integers
    fmt.Println(&nums[0]) // address of the first element
    fmt.Println(&nums[1]) // address of the second element
    fmt.Println(&nums[2]) // address of the third element
}

It will give you something like this:

0xc00000a0f0
0xc00000a0f4
0xc00000a0f8

32 bits are 4 bytes, so the addresses of the elements differ by 4 bytes as well.

In the example above, we used &nums[0] to get the address of the first element. You might wonder what happens if you take the address of the array itself, using &nums:

fmt.Println(&nums)

At first glance, you might expect this to give you the same result as &nums[0], like in C where arrays often “decay” into pointers. But Go is different:

• &nums is a pointer to the entire array (type *[3]int32).

• &nums[0] is a pointer to the first element (type *int32).

When you print &nums, the fmt package recognizes it as a pointer to an array and shows the array’s contents (&[1 2 3]) rather than a raw memory address.

In Go, arrays and pointers to arrays are distinct types, and &nums is of type *[3]int32, not *int32. When you print &nums, fmt recognizes it as a pointer to an array and displays the array's contents, not the address. If you want the address of the first element, you use &nums[0], which is of type *int32.

If you try to access an out-of-bounds index, your program will panic at runtime with an error:

package main

import "fmt"

func main() {
    nums := [3]int32{1, 2, 3}
        i := 4
    fmt.Println(&nums[i])
}

panic: runtime error: index out of range [4] with length 3

goroutine 1 [running]:
main.main()
        C:/projects/Articles/Go Context/main.go:8 +0x3d
exit status 2

This behavior is called bounds checking: before Go reads or writes an array element, it ensures the index is within the valid range (0 up to len(array)-1). If it’s not, the program immediately panics instead of letting you access memory that doesn’t belong to the array.

Bounds checking is important because it:

• Prevents memory corruption: in languages like C, out-of-bounds access can overwrite unrelated memory and cause hard-to-find bugs or security issues.

• Makes programs safer by default: Go will stop execution right away rather than let invalid memory access continue silently.

• Helps debugging: the panic message clearly shows the invalid index and the array’s length, so you can quickly track down the bug.

• It trades a small runtime cost for much greater safety and reliability.

Like every other data structure in Go, arrays are passed by value, meaning that when you pass an array to a function, a copy is made. This can lead to performance issues, so for large arrays, it's often better to pass a pointer to the array instead.

Multi-dimensional Arrays

Multi-dimensional arrays let you model data that naturally fits into rows and columns (or higher dimensions). Some common uses include:

• Matrices and grids

• Images and pixel data in 2D or 3D

• Static lookup tables

Go supports multi-dimensional arrays, which are essentially arrays of arrays. Here's an example:

package main

import "fmt"

func main() {
    var matrix [2][3]int // 2x3 matrix
    matrix[0][0] = 1
    matrix[0][1] = 2
    matrix[0][2] = 3
    matrix[1][0] = 4
    matrix[1][1] = 5
    matrix[1][2] = 6
    fmt.Println(matrix)
}

In this example, we create a 2x3 matrix (2 rows and 3 columns) and initialize its elements. You can access elements using two indices: the first for the row and the second for the column. This can be extended to more dimensions too, but the size of each dimension must be known at compile time.

Limitations

The greatest limitation of arrays in Golang is that their size must be known at compile time. Once it’s declared, the size can’t be changed. Because of this rigidity, arrays are rarely used directly.

When Arrays Are Useful

Despite their rigidity, arrays have a few niche but important use cases in Go:

• Fixed-size data like IP addresses

• Low-level data structures

• Interop with C or system calls

Slices in Go

Because arrays are fixed-size, Go introduced slices: flexible, dynamic sequences built on top of arrays. Think of slices as views into arrays. A slice keeps three things:

1. Pointer: A reference to the underlying array.

2. Length: The number of elements in the slice.

3. Capacity: The maximum number of elements the slice can hold (which is always greater than or equal to the length).

Unlike arrays, a slice's length and capacity can change dynamically as you add or remove elements.

When to Use Slices

In practice, slices are the default way to work with collections in Go. You’ll use them when:

• You don’t know the size of the collection in advance.

• You need to grow or shrink the collection over time.

• You want to pass around subsections of an array without copying data.

• You want idiomatic Go code (most Go APIs accept and return slices, not arrays).

Arrays are mainly useful when you need a fixed size known at compile time (like a 16-byte UUID). For almost everything else, slices are the go-to choice.

How to Declare a Slice

var s []int           // slice of integers
fmt.Println(s)        // []
fmt.Println(len(s))   // length: 0
fmt.Println(cap(s))   // capacity: 0

With var s []int you are declaring a slice. That means you’ve introduced a variable s of type “slice of int” ([]int), but you haven’t yet given it any backing array. At this point, s is nil – it doesn’t point to any actual storage. That’s why its length and capacity are both zero, until you allocate or append to it.

Note that you can also declare a slice using var s[]int{} which initializes the slice with zero elements, but you can’t create an empty array using this syntax: var s[...]int{}. The latter is invalid in Go: you can’t use [...] with var and an empty initialiser!

Allocate (with make)

s := make([]int, 3) // length 3, capacity 3
fmt.Println(s)      // [0 0 0]

Here, Go creates an underlying array of size 3 and makes s point to it. Now s has length 3 and capacity 3.

You can also specify a larger capacity:

s := make([]int, 3, 5) // length 3, capacity 5
fmt.Println(s)         // [0 0 0]
fmt.Println(len(s))    // length: 3
fmt.Println(cap(s))    // capacity: 5

The built-in make function is Go’s way of allocating and initializing certain composite types: slices, maps, and channels. Unlike new, which gives you a pointer to a zeroed value, make sets up the internal data structures those types need to work.

For slices, make does three things under the hood:

1. Allocates an array of the given size (either the length you specify, or the capacity if you provide both).

2. Creates a slice header (pointer, length, capacity) that points to that array.

3. Returns the slice header, ready to use.

Append Elements

One of the main reasons slices are so useful compared to arrays is that they can grow dynamically. In practice, you’ll often start with a slice of a certain length and then need to add more elements later. Again, this is something arrays don’t allow.

Go provides the built-in append function for this. append takes an existing slice and one or more new elements, and returns a new slice with those elements added:

s := make([]int, 3, 5)  // create [0 0 0]
s = append(s, 1)
s = append(s, 2, 3)
fmt.Println(s)          // [0 0 0 1 2 3]
fmt.Println(len(s))     // length: 6
fmt.Println(cap(s))     // capacity: 10 - may be different, depending on the Go version and implementation, but generally it will double when exceeded

If there’s enough capacity, append just writes into the existing array. If not, Go automatically allocates a new larger array, copies the old elements over, and adds the new value. That’s why a slice can grow even though arrays themselves are fixed-size. On one hand, this provides flexibility, but it can also lead to performance overhead due to the need for memory allocation and copying.

To mitigate this, it's a good practice to preallocate slices with an appropriate capacity when you know the size in advance.

How to Slice Slices

In Golang, you can create a new slice by slicing an existing one. You can do this using the [:] operator. The syntax is slice[low:high], where low is the starting index (inclusive) and high is the ending index (exclusive). If low is omitted, it defaults to 0. If high is omitted, it defaults to the length of the slice:

s := []int{1, 2, 3, 4, 5}
s1 := s[1:4] // [2 3 4]
s2 := s[:3]  // [1 2 3]
s3 := s[2:]  // [3 4 5]
fmt.Println(s1, s2, s3)

If two slices share the same underlying array, changes to the elements of one slice will be reflected in the other. This is because both slices point to the same data in memory. For example:

s := []int{1, 2, 3, 4, 5}
s1 := s[1:4] // [2 3 4]
s2 := s[2:]  // [3 4 5]
s1[0] = 10
fmt.Println(s)  // [1 10 3 4 5]
fmt.Println(s2)  // [10 3 4 5]

Inner Representation of Slices

Internally, a slice is represented by a struct that contains a pointer to the underlying array, the length of the slice, and its capacity:

type slice struct {
    ptr *ElementType  // pointer to underlying array
    len int
    cap int
}

This allows slices to be lightweight and efficient, as they don't require copying the entire array when being passed around, just the pointer to the array (and length and capacity). This is often a source of confusion: passing a slice to a function feels like passing by reference, as the values are not copied – but the slice struct itself is still passed by value:

package main

import "fmt"

func modify(s1 [3]int, s2 []int) {
    s1[0] = 99
    s2[0] = 99
}

func main() {
    nums_array := [...]int{1, 2, 3} // array of 3 integers
    nums_slice := []int{1, 2, 3}    // slice of 3 integers
    modify(nums_array, nums_slice)
    fmt.Println(nums_array)         // Output: [1 2 3] - only modified the copy
    fmt.Println(nums_slice)         // Output: [99 2 3] - modified the value in the original slice
}

How to Copy Slices

Copying a slice creates a new slice with the same elements. You can do this using the built-in copy function:

s1 := []int{1, 2, 3}
s2 := make([]int, len(s1))
copy(s2, s1)      // copies elements from s1 to s2
fmt.Println(s2)   // [1 2 3]

Common pitfalls when copying slices:

• Capacity: When copying a slice, the capacity of the destination slice is not automatically adjusted. If the destination slice has a smaller capacity than the source slice, it will only copy up to the capacity of the destination slice.

• Nil Slices: If the source slice is nil, the copy function will not panic, but the destination slice will remain unchanged.

• Overlapping Slices: If the source and destination slices overlap, the behavior is undefined. To avoid this, make sure to copy to a separate slice.

Multi-dimensional Slices

Just like multi-dimensional arrays, you can create multi-dimensional slices, which are essentially slices of slices:

matrix := [][]int{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9},
}
fmt.Println(matrix)

Or:

rows := 3
cols := 4
matrix := make([][]int, rows)
for i := range matrix {
    matrix[i] = make([]int, cols)
}

Multi-dimensional slices are useful when you need flexible, dynamic grids of data. Common use cases include:

• Representing game boards (for example, Tic-Tac-Toe, Minesweeper). This could be done with an array, too.

• Mathematical matrices where the size isn’t fixed.

• Jagged arrays, where each row can have a different length.

Because slices can grow and shrink, they’re generally preferred over multi-dimensional arrays unless you need a fixed size known at compile time.

Slices vs Arrays

Let’s recap the key differences between slices and arrays in Go:

1. Size: Arrays have a fixed size, while slices can grow and shrink dynamically.

2. Memory: Arrays are value types and are copied when passed to functions, while slices are reference types and only the slice header is copied.

3. Flexibility: Slices provide more flexibility and are generally preferred over arrays for most use cases.

Maps in Go

A map is Go's built-in associative data type (hash table). It stores key-value pairs with fast average-time lookups.

Unlike arrays and slices, which are indexed only by integers, maps let you use more meaningful keys such as names, IDs, or other comparable values. This makes them ideal when you need to look up, group, or count data quickly, for example, storing user ages by username, counting word frequencies in text, or mapping product IDs to their prices.

How to Declare a Map

m := make(map[string]int)  // a map with string keys and int values
m["alice"] = 23
m["bob"] = 30
fmt.Println(m)             // map[alice:23 bob:30]

Here, we create a map with string keys and int values. We can add key-value pairs to the map using the syntax m[key] = value. The make function is used to initialize the map. When we print the map, we see the key-value pairs in the output.

Keys can be of any type that is comparable (for example, strings, integers, structs). But they can’t be slices, maps, or functions.

A key in a map must be unique. If you assign a value to an existing key, it will overwrite the previous value.

How to Access Values

Once you have a map, you can retrieve a value using its key with the syntax map[key]:

age := m["alice"]
fmt.Println(age) // 23

If the key doesn't exist, you get the zero value:

age := m["charlie"]
fmt.Println(age) // 0

Here’s what happens under the hood:

1. Go computes the hash of the key ("alice") to find which bucket in the hash table to look in. A bucket is a small container within the hash table that holds one or more key-value pairs. When multiple keys hash to the same bucket, they are stored together inside it.

2. It searches the bucket for the key.

3. If the key exists, Go returns the associated value (23 in this case).

4. If the key doesn’t exist, Go returns the zero value of the map’s value type (0 for int, "" for string, nil for a pointer or slice, and so on).

To distinguish between a key that doesn’t exist and a key whose value happens to be the zero value of the map’s value type, Go provides a second return value when you access a map. Normally, m[key] just returns the value. But if you write:

value, ok := m[key]

• value is the map value for that key (or the zero value if the key is missing).

• ok is a boolean that is true if the key exists in the map, and false if it does not.

You need this because some types have a zero value that is valid in your application. For example, consider a map of usernames to ages:

m := map[string]int{
    "alice": 23,
    "bob":   0,
}

If you try to access "bob" or "charlie" without the second return value:

fmt.Println(m["bob"])     // 0
fmt.Println(m["charlie"]) // 0

Both print 0, so you can’t tell whether "charlie" is missing or "bob" actually has age 0. Using the second return value solves this:

age, ok := m["charlie"]
if !ok {
    fmt.Println("Key not found")
}

Here, ok is false for "charlie" but would be true for "bob". This is a common pattern in Go to safely handle map lookups.

How to Iterate Over a Map

Iterating over a map means going through all key-value pairs in the map, one at a time. You do this with a for loop and the range keyword:

for key, value := range m {
    fmt.Printf("%s: %d\n", key, value)
}

What’s happening here:

• range m produces each key in the map, one by one.

• The loop assigns the current key to key and the corresponding value to value.

• Inside the loop, you can use key and value to process, print, or modify data.

Iterating over a map is useful whenever you need to:

• Process all entries in the map (for example, compute a total, filter items, or apply a transformation).

• Print or display data in key-value format (like logging user ages or product prices).

• Perform aggregate operations, such as counting, summing, or finding the maximum/minimum value.

Important note: Map iteration order in Go is randomized: each loop may produce keys in a different order. This prevents you from relying on insertion order. If you need a deterministic order, you can collect the keys into a slice, sort them, and iterate over the sorted keys.

Inner Representation of Maps

Go maps are implemented as hash tables with buckets:

• Keys are hashed to decide which bucket they go into.

• Each bucket holds multiple key-value pairs.

• When a bucket gets too full, Go splits it into two (similar to dynamic resizing).

• That's why map operations are usually O(1), but not guaranteed constant time.

Just keep in mind that maps are not safe for concurrent writes. If multiple goroutines write to a map at the same time, you’ll get a runtime panic. Use sync.Mutex or sync.RWMutex to protect map access in concurrent scenarios.

If you're interested in how different hash map implementations work under the hood, check out my article on hash maps.

Arrays vs. Slices vs. Maps

Here’s a quick comparison of the feature set of collection types in Go:

Mini Project: Shopping Cart Totals

Let's combine slices and maps into a practical program: given a list of items and their prices, compute the total cost of all items.

The list of items is represented as a slice of strings, and the prices are stored in a map. The key is the item name, and the value is the price:

package main

import "fmt"

func main() {
    items := []string{"apple", "banana", "orange"}
    prices := map[string]float64{
        "apple":  0.99,
        "banana": 0.59,
        "orange": 0.79,
    }

    var total float64
    for _, item := range items {
        total += prices[item]
    }
    fmt.Printf("Total cost: $%.2f\n", total)
}

Total cost: $2.37

This short example shows the synergy between slices (to hold the item names) and maps (to look up prices).

Practice Challenge

Write a function that takes a slice of integers and returns a new slice with duplicates removed. (Solution below.)

Conclusion

Go keeps things simple: with arrays, slices, and maps, you can model almost all everyday data problems.

• Arrays: fixed size, contiguous memory, rarely used directly.

• Slices: flexible, built on top of arrays, your go-to for ordered collections.

• Maps: hash tables for key–value lookups.

You now have the tools to confidently handle collections in Go. The next step? Try writing a small project where you read data from a file, store it in slices, and process it into maps for quick lookups. That's how Go developers handle real-world data.

Practice Challenge Solution

To remove duplicates from a slice, we can keep track of the values we’ve seen in a map and build a new slice containing only the first occurrence of each element:

package main

import "fmt"

func removeDuplicates(intSlice []int) []int {
    seen := make(map[int]bool) // to track seen integers
    result := []int{}
    for _, v := range intSlice {
        if !seen[v] { // if we haven't seen this integer yet, set it to seen and add it to the result
            seen[v] = true
            result = append(result, v)
        }
    }
    return result
}

func main() {
    s := []int{1, 2, 2, 3, 4, 4, 5}
    s = removeDuplicates(s)
    fmt.Println(s) // [1 2 3 4 5]
}

How it works:

• seen keeps track of numbers that have already been added.

• result collects unique numbers as we iterate.

• For each element in the input slice, if it hasn’t been seen, we mark it and append it to result.

• Finally, result contains only unique values.

We just published a comprehensive course on the freeCodeCamp.org channel about data structures and algorithms. This course will help you prepare for coding interviews and strengthen your foundational programming skills. Sheldon Chi developed this course.

Sheldon will break down the most essential data structures and algorithmic patterns. This course will help you build your intuition for efficiency and help you recognize which patterns to apply and how to avoid brute force solutions. And each concept is taught step by step, with practical code walkthroughs and tips for common pitfalls.

Here is the full list of sections in this course:

• Array

• String

• Set

• Control Flow & Looping

• Big O Notation

• Hashmap

• Hashmap practice problems

• Two Pointers

• Two Pointers practice problems

• Sliding Window

• Sliding Window practice problems

• Binary Search

• Binary Search practice problems

• Breadth-First Search (BFS) on Trees

• BFS on Graphs

• BFS practice problems

• Depth-First Search (DFS)

• DFS on Graphs

• DFS practice problems

• Backtracking

• Backtracking practice problems

• Priority Queue/heap

• Priority Queue/heap practice problems

Watch the full course on the freeCodeCamp.org YouTube channel (1-hour course).

This tutorial will teach you how to build a complete game from scratch. You'll implement advanced data structures (Trie), optimize search algorithms (recursion), and create a polished user interface (HTML/CSS). By the end, you will build a fully playable game and learn techniques that you can apply to any web project.

This tutorial covers:

• Implementing a Trie data structure for lightning-fast word search including partial word validation

• Using recursion to efficiently explore millions of possible paths through a game board

• Analyzing 20,000+ dictionary words to create balanced gameplay

• Creating a build system that pre-processes data for better performance

• Building a responsive UI that handles complex user interactions

The Inspiration

When playing Boggle with my family, I have designated myself as the 'checker' of other peoples' words when we are tabulating scores. All of the other players will list the words that they found while I point them out on the board to make sure that they are valid. Once you know that a word is on the board, finding it feels a whole lot easier than searching for it blindly.

I enjoy this process almost as much as playing the game. So, I built a game that focuses on that experience.

The rules are simple. The game presents 49 random letter groupings in a 7x7 grid. Starting with the longest words that can be found, players are presented with words and are asked to find them. Players click on adjacent letter groupings (horizontally, vertically, or diagonally) to form words. Each letter group can be used once per game. The challenge is to find as many valid words as possible in the shortest amount of time.

You can play the finished game here: https://markm208.github.io/wordZearch/.

An Interactive Tutorial on Building Word Zearch

To share how I built Word Zearch, I created "How I Built It: Word Zearch". It is a collection of annotated code playbacks that walk through the entire development process. These playbacks show every line of code I wrote, from implementing the core data structures to polishing the user interface.

To view a code playback, click on the comments in the left panel. Each comment updates the code in the editor and highlights the change. Read the explanation, study the code, and use the built-in AI assistant if you have questions. For more information about code playbacks, you can watch a short demo here.

Prerequisites

You should have some programming experience to follow along. I use object-oriented programming, recursion, and DOM manipulation throughout the tutorial.

If you're new to web development, this offers a complete start-to-finish project that will help put all of the pieces together. If this tutorial moves too fast for you, consider starting with my introductory web development 'book' first: An Introduction to Web Development from Back to Front

What You'll Learn

1. Building a Trie Data Structure

https://playbackpress.com/books/wordzearchbook/chapter/1/1

Learn how to implement a Trie (prefix tree) for fast word validation. This data structure is the foundation of the game's performance.

Starting with a dictionary file, I parse 20,000+ words into a nested object structure. Each level represents a letter position. The implementation includes a search method that returns three values: FOUND, NOT FOUND, or PARTIAL.

This PARTIAL value is crucial. It indicates when the beginning of a dictionary word is found but it is not a complete word. Later on when searching for words on the board, it tells the algorithm when to stop searching, preventing millions of unnecessary operations during gameplay.

2. Modeling Letter Frequencies

https://playbackpress.com/books/wordzearchbook/chapter/1/2

Here, I analyze letter frequencies from the words in the dictionary to create weighted distributions for generating game boards randomly. I start by tracking how often single letters, two-letter combinations, and three-letter combinations appear across all dictionary words. This approach will work for words in any language as long as you have a dictionary file filled with words.

For each word, I extract all possible letter groupings of each size and count their occurrences. After processing the entire dictionary, I sort these groupings by frequency and select the most common ones. To ensure interesting game boards, I create proportional arrays where more frequent letter groups appear multiple times relative to their frequency. I'll use this data to create a balanced game board that reflects real language usage by picking the most used groups of letters at random.

3. A Simple Web App

https://playbackpress.com/books/wordzearchbook/chapter/1/3

In this playback, I set up the foundation for the web application and create an efficient build process. Rather than rebuilding the Trie and calculating letter frequencies every time someone plays the game, I develop a build system that pre-generates these data structures.

Then I reorganize the project by creating a build folder and a template file. The BuildTrie class will read the dictionary, construct the word map and letter frequencies, and inject this data into a template file to generate a static Trie.js file. This approach significantly improves performance since the computationally expensive dictionary processing happens once during the build phase rather than on every page load.

4. Building the Game Board

https://playbackpress.com/books/wordzearchbook/chapter/1/4

Next, I implement the WordBoard class, which manages the 7x7 game board and contains the core algorithm for finding valid words. The board is configured to hold 49 letter groups with customizable distributions of single, double, and triple letter combinations.

The heart of the implementation is a recursive search algorithm in the solve method that explores all possible word paths. Starting from each position on the board, the algorithm moves in eight directions (horizontally, vertically, and diagonally), building up potential words by concatenating adjacent letter groups. To prevent infinite loops and ensure game rules are followed, I track visited positions so each letter group can only be used once per word.

The Trie integration provides a crucial optimization. When a letter sequence isn't found in the Trie, the algorithm stops exploring that path, preventing unnecessary searching. Found words are organized by length in a results array, with each result storing the complete path through the board. The playback concludes with testing the WordBoard, demonstrating how it successfully identifies all valid words that can be formed from the randomly generated letter groups.

5. The Front End

https://playbackpress.com/books/wordzearchbook/chapter/1/5

In this final playback, I build the complete user interface for Word Zearch. I start by creating a 7x7 HTML table where each cell displays a letter group from the WordBoard.

I implement click handling that allows players to select adjacent letter groups, visually highlighting them as they build words. The core gameplay logic compares the player's selected path against the pre-calculated valid word paths from the WordBoard's solve method.

When a match is found, I add visual feedback including directional arrows showing the word's path, color coding for completed words, and preventing reuse of letter groups by marking them as solved. Found words are displayed in a results list with timestamps and links to their definitions. The interface also includes hover effects to highlight previously found words on the board and handles game completion by showing total time and offering a replay option.

The result is a fully interactive word search game with intuitive visual feedback and smooth gameplay.

Start Building

Word games make excellent programming projects. They combine interesting computer science concepts with practical web development skills.

Try playing the game first to understand what I'm building. Then dive into the code playbacks to see how it all comes together. If you get stuck, use the AI assistant like a tutor to help explain what is happening in the code. Afterwards, if you are feeling adventurous, try modifying the code, optimizing it, adding new features, or building your own word game!

Questions and feedback are always welcome here: mark@playbackpress.com

If you'd like to support my work and help keep Playback Press free for all, consider donating using GitHub Sponsors. I use all of the donations for hosting costs. Your support helps me continue creating educational content like this. Thank you!

In this hands-on tutorial, you will learn how to implement queues in TypeScript using linked lists.

Here’s what we’ll cover

• Prerequisites

• Getting started

• What are Queues?

• What are Linked Lists?

• What is a Simple Queue?

• What is a Circular Queue?

• What is a Double Ended Queue?

• What is a Priority Queue?

• When to Use Queues (and When to Avoid Them)

• Conclusion

Prerequisites

1. TypeScript: You need to know TypeScript basics, such as interfaces, types, and classes.

2. Algorithm fundamentals: You need a basic understanding of data structures and algorithms. For example, you should be comfortable analyzing time and space complexity using Big-O notation.

3. Linked Lists Data Structure: It's important to have a solid understanding of linked lists before starting this tutorial. I wrote a detailed linked list tutorial that you can use to learn about this data structure.

Getting Started

To get started with this tutorial, you’ll use a playground project that’s designed to help you implement queues and follow each step hands-on.

Clone the project from the GitHub repository and code along with the tutorial.

The project structure is as follows:

.
├── index.ts
├── examples
│   ├── 01-linked-list.ts
│   ├── 02-simple-queue.ts
│   ├── 03-circular-queue.ts
│   ├── 04-double-ended-queue.ts
│   └── 05-priority-queue.ts
└── playground
    ├── 01-linked-list.ts
    ├── 02-simple-queue.ts
    ├── 03-circular-queue.ts
    ├── 04-double-ended-queue.ts
    └── 05-priority-queue.ts

Throughout the tutorial, you will use the playground directory to implement and test your code.

The examples directory contains the final version of each implementation. If you get stuck, you can look at these solutions as a last resort!

What Are Queues?

A queue is a data structure that manages items in a first-in, first-out (FIFO) order, where the first item added is the first removed.

For example, imagine a printer handling jobs. If you send three documents to print, the printer processes them in the order they arrive. The first document prints first, then the second, and finally the third.

In programming, queues help manage tasks that need to happen in order, such as:

• A web server queues incoming requests to process them one by one.

• A chat app queues messages to send them in the order they’re typed.

• A navigation app queues locations to explore a map level by level. (Breadth-First Search)

There are four types of queues in a data structure:

• Simple Queue: Adds items to the back and removes them from the front in first-in, first-out (FIFO) order.

• Circular Queue: It is similar to a simple queue, except the last element is connected to the first.

• Double-Ended Queue (Deque): Allows adding or removing items from both front and back, like a bus stop line where people join or leave either end.

• Priority Queue: Processes items based on priority, not arrival order. Like a delivery app processes VIP orders before regular ones.

Each of these queues has a set of operations for managing their items. In this tutorial, you will learn about the following common and widely used operations:

• enqueue: Adds an item to the back of the queue, like a new customer joining the end of a ticket line.

• dequeue: Removes and returns the item at the front of the queue.

• getFront: Looks at the item at the front without removing it, like checking who’s first in line.

• getRear: Looks at the item at the back without removing it, like seeing who’s last in line.

• isEmpty: Checks if the queue has no items.

• isFull: Checks if the queue has reached its maximum size.

• peek: Same as getFront, views the front item without removing it, like a quick glance at the first task.

• size: Returns the number of items in the queue, like counting how many people are in line.

Now that you know about queues and their main operations, let's get into the actual implementation and see how it looks in code.

There are a few different ways to implement queues, but in this tutorial, you will learn about linked list-based queues, which use a linked list to create the queues.

First, let's briefly learn about the linked list data structure and then move on to the queue implementation.

What Are Linked Lists?

A linked list is a method of storing a collection of items where each item, known as a "node," contains two parts: the actual data and a reference (or pointer) to the next item in the list.

Unlike arrays, where all items are stored next to each other in memory, linked lists connect nodes using these references, like a chain.

Linked lists are used to implement queues because they allow efficient insertion at the end and removal from the front, which are the two main operations of a queue.

In a linked list-based queue, you can add a new node at the tail and remove one from the head in constant time (O(1)) without needing to shift elements, as you would in an array.

In this tutorial, you are going to use a specific type of linked list called Circular Doubly Linked List.

A circular doubly linked list is a type of linked list where each node connects to both the next and previous nodes, and the last node loops back to the first one to form a circle.

This means you can move through the list in both directions and never hit a dead end. This makes it easy to go forward or backward through nodes and helps avoid special cases like handling null at the ends.

In a circular doubly linked list, everything is connected in a loop, which simplifies certain queue operations and keeps things efficient.

You can learn more about circular linked lists in my Linked Lists Handbook.

For this tutorial, I’ve already added a circular doubly linked list in src/playground/01-linked-list.ts:

// 📁 src/playground/01-linked-list.ts

/**
 * Node for doubly linked list
 */
export class NodeItem<T> {
  value: T;
  next: NodeItem<T> | null = null;
  prev: NodeItem<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

/**
 * Circular Doubly Linked List
 */
export class LinkedList<T> {
  private head: NodeItem<T> | null = null;
  private tail: NodeItem<T> | null = null;
  private currentSize: number = 0;

  /**
   * Add a new node to the front of the list
   * @param value The value to add
   */
  prepend(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.head!.prev = newNode;
      this.tail!.next = newNode;
      this.head = newNode;
    }
    this.currentSize++;
  }

  /**
   * Add a new node to the back of the list
   * @param value The value to add
   */
  append(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.head!.prev = newNode;
      this.tail = newNode;
    }
    this.currentSize++;
  }

  /**
   * Remove and return the value from the front of the list
   * @returns The value at the head or undefined if empty
   */
  deleteHead(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.head!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head!.next;
      this.head!.prev = this.tail;
      this.tail!.next = this.head;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Remove and return the value from the back of the list
   * @returns The value at the tail or undefined if empty
   */
  deleteTail(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.tail!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail!.prev;
      this.tail!.next = this.head;
      this.head!.prev = this.tail;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Get the value at the front without removing it
   * @returns The value at the head or undefined if empty
   */
  getHead(): T | undefined {
    return this.head?.value;
  }

  /**
   * Get the value at the back without removing it
   * @returns The value at the tail or undefined if empty
   */
  getTail(): T | undefined {
    return this.tail?.value;
  }

  /**
   * Check if the list is empty
   * @returns True if the list is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.currentSize === 0;
  }

  /**
   * Get the current size of the list
   * @returns The number of nodes in the list
   */
  size(): number {
    return this.currentSize;
  }
}

In this module, you have a circular doubly linked list with 8 different methods that will make it easier to build queues later in the tutorial:

• prepend: Adds a new value to the front of the list.

• append: Adds a new value to the end of the list.

• deleteHead: Removes and returns the value at the front.

• deleteTail: Removes and returns the value at the end.

• getHead: Returns the front value without removing it.

• getTail: Returns the end value without removing it.

• isEmpty: Checks whether the list has no items.

• size: Returns the number of items currently in the list.

Now that your linked list is ready, let's begin creating your first queue!

What is a Simple Queue?

A Simple Queue follows the basic FIFO rule: you’ll to add items to the back and remove them from the front.

It’s like a line of customers at a ticket counter, where the first person in line buys a ticket first.

To get started, open src/playground/02-simple-queue.ts, where you will find the placeholder for the Simple Queue with its methods:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  ...methods
}

At the core of this SimpleQueue class, you're using a circular doubly linked list to store the items, and optionally allowing a maximum size limit to control how big the queue can grow.

• private list: LinkedList<T> is where the queue's data is stored. Instead of a simple array, you're using a custom linked list, which makes it efficient to add or remove items from either end. The linked list manages the data structure and allows you to focus on how the queue works.

• private maxSize is an optional limit for how many items the queue can hold. If not provided, the queue can grow as large as needed.

• Then, the constructor method that runs when you create a new queue. It creates a new, empty linked list to hold the queue items.

Now, let's implement the queue methods.

Open your code editor and update src/playground/02-simple-queue.ts with the following code:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

As you can see, the linked list greatly simplifies your queue implementation because it acts as the engine behind your queue.

Here's how your Simple Queue works:

• isEmpty(): This method checks whether the queue contains any items. It calls the isEmpty() method on the linked list, which internally checks if the current size of the list is zero. If the list has no nodes, it returns true, indicating that the queue is empty. This is a basic utility method often used before attempting to dequeue or inspect the queue.

• isFull(): This method determines whether the queue has reached its capacity. It compares the current size of the linked list (via the size() method) to the optional maxSize value. If maxSize is defined and the size is equal to or greater than that limit, it returns true, indicating that no more items can be added. This is useful to prevent overflow in bounded queues.

• size(): This method returns the number of items currently stored in the queue. It directly calls the size() method of the linked list, which tracks how many nodes are present. This allows you to monitor queue usage and remaining capacity.

• enqueue(): This method adds a new item to the end (rear) of the queue. It first checks whether the queue is full by calling the isFull() method. If it is, the method throws an error. Otherwise, it appends the new item to the internal linked list using the append() method, which adds the new node to the tail of the circular doubly linked list.

• dequeue(): This method removes and returns the item at the front of the queue. It calls the deleteHead() method of the linked list, which removes the head node and updates the links of the surrounding nodes to maintain the circular structure. If the queue is empty, it returns undefined.

• getFront(): This method returns the value at the front of the queue without removing it. It uses the getHead() method of the linked list to retrieve the value of the head node. This operation does not modify the queue and is useful for previewing the next item to be dequeued.

• getRear(): This method returns the value at the rear of the queue without removing it. It uses the getTail() method of the linked list, which returns the value of the tail node. This helps you inspect the most recently added item without altering the queue.

• peek(): This method is an alias for getFront(). It returns the item at the front of the queue without removing it. Internally, it calls getFront() to get the head value. This is often used in queue APIs to check the next item in line.

You’ve just implemented your first queue in TypeScript. To make sure that your implementation works correctly, run the following command in your terminal at the root of the project:

npm run test:file 02

If any of the tests fail, use the final example from src/examples/02-simple-queue.ts to debug the issue, and then run the tests again.

If all tests pass, you can proceed to the next section, where you'll implement a Circular Queue.

What is a Circular Queue?

A CircularQueue is a fixed-size queue where the last position connects back to the first. This allows you to reuse space after removing items.

Imagine a buffet line with a limited number of plates: when someone takes a plate from the front, a new one is added at the back, using the same space again.

The CircularQueue is quite similar to the SimpleQueue, but it has a few unique differences.

Let’s modify src/playground/03-circular-queue.ts and add the following code:

// 📁 src/playground/03-circular-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Circular Queue implemented with a circular doubly linked list
 */
export class CircularQueue<T> {
  private list: LinkedList<T>;
  private maxSize: number;

  /**
   * @param maxSize Required maximum size of the circular queue
   */
  constructor(maxSize: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Circular queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

This may look very similar to a SimpleQueue, but there are a few key differences:

• Constructor Difference: Unlike the SimpleQueue, the CircularQueue requires a maxSize parameter during instantiation. This enforces a strict upper limit on how many elements can be in the queue at once.

  In contrast, SimpleQueue treats maxSize as optional and allows unbounded queues. By making the size mandatory, CircularQueue is better suited for fixed-size buffer scenarios where memory or resource control is important (for example, in real-time systems or caching).

• enqueue(): This method is almost identical to the one in SimpleQueue, but the key difference lies in the design intent. In CircularQueue, throwing an error when the queue is full is part of the contract and it assumes that you’re managing a fixed buffer.

  The circular nature comes into play conceptually: once full, no more data can enter unless older entries are removed, which mimics a circular overwrite mechanism (though this specific implementation doesn’t auto-overwrite).

• isFull(): This method behaves the same as in SimpleQueue when a maxSize is set, but in CircularQueue, it’s always applicable because maxSize is required. The consistent presence of a size limit makes the queue predictable and ideal for bounded use cases like streaming data and rate-limited processing.

Now, let's test the implementation to see if it works:

npm run test:file 03

If any of the tests fail, use the final /examples directory to debug the issue.

If the tests pass, you'll be ready to move on to the next section, where you will learn about double-ended queues.

What is a Double Ended Queue?

A double-ended queue (deque) lets you add or remove items from both the front and the back.

It’s like a line at a bus stop where people can join or leave from either end.

Let’s modify src/playground/04-double-ended-queue.ts and add the following code:

// 📁 src/playground/04-double-ended-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Double-Ended Queue (Deque) implemented with a circular doubly linked list
 */
export class Deque<T> {
  private list: LinkedList<T>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the deque
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<T>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the front of the deque
   * @param item The element to add
   */
  enqueueFront(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.prepend(item);
  }

  /**
   * Add an element to the rear of the deque
   * @param item The element to add
   */
  enqueueRear(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the deque
   * @returns The element at the front or undefined if empty
   */
  dequeueFront(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Remove and return the element from the rear of the deque
   * @returns The element at the rear or undefined if empty
   */
  dequeueRear(): T | undefined {
    return this.list.deleteTail();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the deque is empty
   * @returns True if the deque is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the deque is full
   * @returns True if the deque is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the deque
   * @returns The number of elements in the deque
   */
  size(): number {
    return this.list.size();
  }
}

Now, let's go through the methods:

• enqueueFront(): This method allows adding an element to the front of the deque, unlike in SimpleQueue or CircularQueue which only support adding to the rear. Internally, it uses list.prepend(item) to insert the item at the head.

  This operation makes the deque suitable for use cases where elements need to be pushed and popped from both ends, like in undo/redo systems or task schedulers.

• enqueueRear(): This behaves similarly to SimpleQueue’s enqueue, adding elements to the rear using list.append(item).

  The distinction in Deque is that this is just one of two symmetric operations and it gives you full double-ended control.

• dequeueFront(): This removes and returns the element from the front of the deque using list.deleteHead().

  While similar to the dequeue method in queues, the naming here is explicit to clarify that it's operating on the front and can be paired with a rear counterpart.

• dequeueRear(): This is a unique feature to deques, it removes and returns the element at the rear using list.deleteTail(). This complements dequeueFront() and enables LIFO (stack-like) behavior if needed.

• Constructor Difference: Like SimpleQueue, the Deque accepts an optional maxSize. This allows for flexible configurations.

  You can have unbounded deques when maxSize is not provided, or fixed-size deques when constraints are important. This is in contrast to CircularQueue, which requires a max size.

Once you have completed the implementation, run the following command to test the module:

npm run test:file 04

Now, you're ready to move on to the last section of the tutorial, where you'll learn about the Priority Queue.

What is a Priority Queue?

A priority queue processes items based on their priority, not their order of arrival.

Higher-priority items are removed first, like an emergency room where patients with severe conditions are treated before others.

Let’s modify src/playground/05-priority-queue.ts:

// 📁 src/playground/05-priority-queue.ts

import { LinkedList, NodeItem } from "./01-linked-list";

/**
 * Interface for an element with priority
 */
interface PriorityItem<T> {
  value: T;
  priority: number;
}

/**
 * Priority Queue implemented with a circular doubly linked list
 */
export class PriorityQueue<T> {
  private list: LinkedList<PriorityItem<T>>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the priority queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList<PriorityItem<T>>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the queue based on its priority
   * Higher priority numbers are dequeued first
   * @param value The value to add
   * @param priority The priority of the value (higher number = higher priority)
   */
  enqueue(value: T, priority: number): void {
    if (this.isFull()) {
      throw new Error("Priority queue is full");
    }

    const newItem: PriorityItem<T> = { value, priority };
    if (this.isEmpty()) {
      this.list.prepend(newItem);
      return;
    }

    let current = this.list["head"];
    let count = 0;
    while (
      current &&
      current.value.priority >= priority &&
      count < this.size()
    ) {
      current = current.next;
      count++;
    }

    if (count === this.size()) {
      this.list.append(newItem);
    } else {
      const newNode = new NodeItem(newItem);
      newNode.next = current;
      newNode.prev = current!.prev;
      if (current!.prev) {
        current!.prev.next = newNode;
      } else {
        this.list["head"] = newNode;
      }
      current!.prev = newNode;
      if (current === this.list["head"]) {
        this.list["head"] = newNode;
      }
      this.list["tail"]!.next = this.list["head"];
      this.list["head"]!.prev = this.list["tail"];
      this.list["currentSize"]++;
    }
  }

  /**
   * Remove and return the element with the highest priority from the queue
   * @returns The value with the highest priority or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead()?.value;
  }

  /**
   * Get the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead()?.value;
  }

  /**
   * Get the element with the lowest priority without removing it
   * @returns The value at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail()?.value;
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

Let's understand how the methods work within a Priority Queue:

• enqueue(): This method inserts a new element into the queue based on its priority. Unlike other queue types where order is based on insertion time, PriorityQueue uses a sorting mechanism where elements with higher priority values are placed closer to the front.

  The method traverses the linked list from the head, searching for the correct position where the new item should be inserted so that the list remains sorted in descending priority order.

  It manually adjusts the prev and next pointers to keep the circular doubly linked list intact. This sorting during insertion ensures quick access to the highest priority element later.

• dequeue(): This method removes and returns the element with the highest priority, which is always positioned at the front of the list.

  Internally, it calls deleteHead() and then returns the value from the PriorityItem<T> node. Because items are sorted during insertion, this operation is always efficient and retrieves the correct item.

• getFront(): This retrieves the value at the front of the queue without removing it. Since the list is sorted in descending priority, this value always represents the highest priority item.

• getRear(): This returns the value at the rear of the queue, which is the item with the lowest priority. It accesses the last element in the list using getTail() and extracts the value.

• isEmpty(): This checks whether the queue contains any elements by delegating to the linked list’s isEmpty() method.

• isFull(): This checks whether the queue has reached its maximum allowed size. It compares the current size with maxSize if it's defined.

• peek(): This is functionally equivalent to getFront(). It provides a clearer semantic name when users want to examine the highest-priority element without removing it.

• size(): This returns the total number of items currently in the priority queue. It's useful for monitoring capacity or debugging.

• Key Differences: The priority queue differs from other queue types by enforcing order during insertion based on a numeric priority.

  This enables constant-time access to the highest priority element but introduces linear-time insertion complexity due to the need to find the correct place for each new element.

  It supports advanced scheduling and load balancing use cases where task urgency or importance matters more than arrival time.

Once you’re done with the implementation, run the following command to test your code:

npm run test:file 05

That’s it, congratulations!

You have successfully completed the tutorial and learned about queues and their different variations. Great job!

Before reaching conclusions, let’s briefly learn about where to use queues and where to avoid them. We’ll also discuss the bottlenecks and issues that queues may create if not used correctly and in the right place.

When to Use Queues (and When to Avoid Them)

Queues are ideal in scenarios where tasks or data must be processed in the exact order they arrive, such as in job scheduling and event handling systems.

For example, when multiple print jobs are sent to a printer, a queue can make sure each document is printed in the order it was submitted.

Similarly, queues are used in operating systems for managing tasks in thread pools or CPU scheduling (for example, Round Robin), where order is crucial.

Queues are also heavily used in asynchronous communication systems such as message brokers like RabbitMQ and Kafka.

In these systems, producers and consumers operate independently: a producer pushes messages into the queue, and a consumer processes them later.

This pattern is extremely useful in microservices architecture or serverless environments, where different parts of a system need to remain loosely coupled and highly scalable.

Similarly, in real-time systems like video streaming or sensor data ingestion, queues help buffer incoming data to avoid data loss and allow for smooth downstream processing.

When to Avoid Queues

Queues are not well-suited for problems that require random access to elements, complex search operations, or sorting.

Since queues typically allow insertion at one end and removal from the other, they’re inefficient for use cases where you frequently need to access elements in the middle or search through all items.

An array, tree, or hash map would serve better in such cases.

Using queues inappropriately can introduce unnecessary complexity and hidden bottlenecks.

For instance, blindly placing a queue between every microservice might decouple components but also make debugging and failure handling more difficult.

Over-queuing can also lead to backpressure problems where queues grow uncontrollably under high load which will increase latency or even crashing the system if not managed properly.

So you should use queues deliberately: when order, buffering, or async processing is required.

Conclusion

Queues are a basic data structure that work well when you need order and async processing.

Queues are useful for handling tasks, streaming data, or coordinating services, and making sure things run smoothly and efficiently.

But they aren't suitable for every problem. It's important to understand their pros and cons to use them correctly and avoid unnecessary complexity.

Thanks for following along with this tutorial. You can follow me on X, where I share more useful tips on data structures and web development.

Happy coding!

Behind that seamless rerouting is a graph – not a chart, but a structure of nodes (places) and edges (roads) that allows Google Maps to calculate the shortest, fastest, or least congested path from point A to point B.

Once you start noticing them, you’ll realize graphs are everywhere. If you’ve ever used:

• Google Maps to get from one city to another,

• LinkedIn to see how you’re connected to someone,

• or Git to visualize branches and merges…

…you’ve interacted with a graph.

Graphs are everywhere, in how we plan routes, recommend friends, manage project dependencies, and even predict the possible moves of a knight on a chessboard. But to use them well, we first need to understand how they’re structured and why they’re so useful.

In this article, you’ll learn:

• What a graph is and how it’s used in real-world systems

• The different types of graphs and how they’re represented in code

• How to traverse graphs using search algorithms

• And finally, how a knight’s movement in chess can be modeled using graphs, and solved using traversal techniques

Let’s start by breaking down what graphs are made of and why they show up in so many things you already use.

Table of Contents

• What is a Graph?

• Types of Graphs

• How Graphs Are Represented

• Graph Traversal

• Knight's Travails: A Real-World Graph Problem

• Wrapping Up

Prerequisites

This article is beginner-friendly, and no prior knowledge of graphs is required. To follow along with the code examples, it helps to have:

• Some familiarity with data structures like stacks and queues.

• I use Python for the code snippets, but if you’ve worked with another language, you should be able to follow along easily.

What is a Graph?

At its core, a graph is a collection of nodes (also called vertices) and edges – connections that link those nodes together.

If it sounds simple, that’s because it is. The power of graphs isn’t in their complexity, it’s in their flexibility. You can use them to represent almost anything: people, cities, web pages, tasks, game moves, and the relationships between them.

Let’s break it down:

Nodes (Vertices)

Each node is a point in the graph. It might represent:

• A location (like a city on a map)

• A person (in a social network)

• A page (for example, on the web)

• A square (like one on a chessboard)

Edges

An edge is a connection between two nodes. It could represent:

• A road between two cities

• A friendship between two users

• A hyperlink between two web pages

• A legal knight move between two squares

Edges can have direction (one-way or two-way), weight (like distance or cost), or be simple and unweighted.

Graph Visualizer

Here’s a simple graph:

In this image:

• The circles represent nodes (also called vertices)

• The lines connecting them are edges, which show that two nodes are related or connected in some way

Each node is connected to one or more other nodes, forming a network of relationships.

Types of Graphs

Now that we’ve seen what a graph looks like, let’s talk about the different ways graphs can behave.

Graphs can vary in direction, weight, and structure. Understanding these types helps us choose the right graph model for the problem we’re trying to solve.

Directed Graphs

In a directed graph (also known as a digraph), connections between nodes move in a specific direction. Think of it like a one-way street – if you can drive from Point A to Point B, that doesn't necessarily mean you can drive back the same way.

A good example of this is X (Twitter). If you follow someone on X, it doesn’t automatically mean they follow you back. Your “follow” is a one-way connection, a directed edge from you to them.

This kind of graph is especially useful in situations where relationships are not mutual. On the internet, links between web pages behave the same way. Page A might link to Page B, but Page B might not link back. Similarly, in workflow systems or task pipelines, each step flows into the next in a specific order, and you generally don’t loop back – Step 1 leads to Step 2, and so on.

Undirected Graphs

An undirected graph represents relationships that go both ways. If there’s a connection between node A and node B, you can travel in either direction.

A common example is a friendship on Facebook. If you’re friends with someone, the connection is mutual by default. It wouldn’t make sense to be “half-friends”.

Undirected graphs are useful when the relationship itself is mutual and symmetrical, like shared devices on a network or road systems where travel is allowed both ways.

The key difference here is that edges are just lines, not arrows – they don’t imply flow or hierarchy, just connection.

Weighted Graphs

A weighted graph is one where each connection (edge) carries extra information, usually a number representing distance, cost, time, or importance.

Consider how you use Google Maps to get from one location to another. The app doesn’t just look for any route, it looks for the one that takes the least time, travels the shortest distance, or uses the least fuel. All of those are weights.

In a graph like this, two cities might be connected, but one road might take 5 minutes while another takes 20, so the edge between those cities isn’t just a line – it’s a line with a value.

This structure lets us make smarter decisions. We can ask questions like:

• What’s the cheapest way to reach a destination?

• Which route avoids the most traffic?

• What’s the fastest route from node A to node Z?

If undirected and directed graphs describe who is connected to whom, weighted graphs help us understand how strong, far, or costly those connections are.

Unweighted Graphs

In an unweighted graph, all edges are treated equally. A connection either exists, or it doesn’t – there’s no extra value or cost attached.

Think of a group of friends where you only care about whether two people know each other. You’re not trying to measure how close they are or how often they talk, you just want to map the presence or absence of a relationship.

Unweighted graphs are useful for modeling systems where the existence of a connection is more important than any nuance of how strong it is. These are great for representing basic relationships, board game states, or decision trees where each path is considered equally likely or valuable.

In short, unweighted graphs are all about the “yes/no,” not the “how much.”

Cyclic Graphs

A cyclic graph is one where it’s possible to loop back to where you started. You can travel through a series of connections and eventually end up at the same node.

If you’ve ever looked at a city map or used a public transit system with circular routes, you’ve seen a cycle in action. You might start at a station, ride the train through several stops, and eventually return to where you began, without ever retracing your exact steps.

Cyclic graphs are especially useful in simulations, games, or real-world systems where loops are part of the design, like control circuits or repeated workflows. They’re a natural fit for any scenario where repetition or return paths matter.

But they can also introduce complexity, especially in algorithms that aren’t meant to handle cycles. Recognizing whether your graph has cycles is often an important first step in choosing the right traversal method.

Acyclic Graphs

An acyclic graph is the opposite of a cyclic one – there are no loops. Once you start moving through the graph, you can’t return to a node you’ve already visited by following the direction of the edges. They can either be directed or undirected graphs.

Think of task management systems where some tasks depend on others. You can't complete Task C until you’ve finished Task B, and you can't start B until A is done. There’s a natural order, and no looping back.

Acyclic graphs are common in:

• Scheduling systems

• Organizational charts

• Tutorial progression systems (like one chapter unlocking the next)

Directed Acyclic Graphs

A Directed Acyclic Graph or DAG is a type of acyclic graph where every edge has a direction, and you can’t form any cycles. It’s like a roadmap where all roads point forward and never loop.

This structure is incredibly common in computing, especially when you need to track progress, dependencies, or history.

In Git, for example, every commit points to one or more parent commits, forming a directed graph of changes. But since commits can’t “revisit” an earlier state, the structure remains acyclic.

In package managers, a library might depend on others, but you can't have a loop. Say library A depends on B, which depends on C, which depends on A again – that would break everything. A DAG ensures that dependencies move forward, not in circles.

How Graphs Are Represented

So far, we’ve explored graphs as concepts and visuals with various types and behaviors. But when it’s time to work with graphs in code, we need a way to represent those connections in a structured format.

There are two common ways to represent a graph:

• Adjacency List

• Adjacency Matrix

Each has its strengths, and which one you use depends on the type of graph and what operations you need to perform.

Adjacency List

An adjacency list stores a graph as a collection of nodes, where each node maps to a list of its neighbors (nodes it’s connected to). An adjacency list is one of the most intuitive ways to represent a graph. But how you write this list depends on the type of graph you’re working with.

For an undirected graph, the connection goes both ways, so each edge is written twice – once for each node.

For a directed graph, each connection only flows one way, so you only write it once, in the direction it points.

Benefits:

• Memory-efficient for sparse graphs (that is, not all nodes are connected)

• Easy to add or remove nodes and edges

• Fast to get a node’s neighbors – just read its list

Downsides:

• Slower edge lookup: To check if two nodes are connected, you have to scan a list

• Can be inefficient for dense graphs where most nodes connect to many others

• Sorting neighbors or accessing them by index is less convenient

Adjacency Matrix

An adjacency matrix uses a 2D array (or grid) to represent connections between nodes. Each row and column corresponds to a node, and the cell at the intersection tells you whether there’s a connection.

• A value of 1 means there is an edge between the two nodes.

• A value of 0 means an edge doesn’t exist between two nodes.

For an undirected graph, an edge between i and j means the connection works both ways. So if (i, j) is 1, (j, i) is also 1. This makes the matrix symmetric, that is, (i, j) == (j, i).

For a directed graph, an edge from node i to node j is at position (i, j). But this doesn’t imply that there's an edge from j to i. So in general, (i, j) ≠ (j, i).

Benefits:

• Instant edge lookup between any two nodes in O(1) time.

• Simple to implement and often used in low-node-count, dense graphs.

Downsides:

• High space complexity – even if the graph has few edges, the matrix still takes up O(V²) space.

• Inefficient for sparse graphs, where many cells are unused.

• Finding neighbors requires scanning an entire row, which takes O(V) time.

Graph Traversal

Once you’ve built a graph using adjacency lists or matrices, the next question is: how do you explore it?

Graph traversal is the process of visiting each node (and its neighbors) in a graph in a specific order. It’s a foundational technique in computer science, used in everything from web crawling to friend suggestions on social media.

Traversal is used when:

• You want to search for a specific value or node.

• You want to visit all nodes, for example, to analyze connectivity.

• You want to solve puzzles, like mazes or routing problems.

There are two primary ways to traverse a graph: Depth-First Search (DFS) and Breadth-First Search (BFS). Let’s traverse through this graph using both methods:

Breadth-First Search (BFS)

BFS starts from a node and explores all of its immediate neighbors before moving on to the neighbors of those neighbors.

It’s commonly used in:

• Finding the shortest path (in unweighted graphs)

• Level-order traversal

• Network broadcast simulations

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        # node has not been visited
        if node not in visited:
            print(node)  # Visit the node
            visited.add(node)
            for neighbor in graph[node]:  # Look at each neighbor of the current node
                if neighbor not in visited:     
                    queue.append(neighbor)  

# Undirected graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'E'],
    'E': ['D']
}

bfs(graph, 'A')

Here’s the output of the code above:

A
B
C
D
E

What This Code Does:

Step 1: Choose a Starting Point
Pick the node where you want to begin the traversal. Add it to a queue.

Step 2: Visit the Node at the Front of the Queue
Take the first node from the queue (this is your current node) and mark it as visited. Do something with it, like printing its value.

Step 3: Add Its Neighbors to the Queue
Look at all the nodes directly connected to the current node (its neighbors). For each neighbor, if it hasn't been visited yet, add it to the end of the queue.

Step 4: Repeat Until the Queue Is Empty
Go back to Step 2. Keep visiting the node at the front of the queue and enqueue its unvisited neighbors until no more nodes are left in the queue.

Depth-First Search (DFS)

DFS dives deep into one path of the graph before backtracking and exploring other branches.

It’s useful for:

• Cycle detection

• Topological sorting

• Solving puzzles like mazes (where the shortest path doesn’t matter)

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)  # Visit the node
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)


# Example graph (same as before)
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'E'],
    'E': ['D']
}

dfs(graph, 'A')

Here’s the output of the code above:

A
C
D
E
B

Just like BFS, we:

• Track visited nodes with a set

• Use a loop to process each node

• Visit neighbors one by one

But here’s the important difference: DFS uses a stack, so it goes deep into one path until it can’t go further, then it backtracks and explores the next path. This makes it great for tasks like solving mazes or exploring all possibilities in a decision tree.

Wrapping Up Graph Traversal

Understanding how to traverse a graph is foundational to solving many real-world problems, from mapping routes to analyzing social networks. Whether you're using BFS to find the shortest path or DFS to explore deep relationships, choosing the right traversal method depends on the problem you're trying to solve.

Knight's Travails: A Real-World Graph Problem

To bring graphs to life, let’s start with a simple example.

Imagine you're playing chess, and your knight is stuck in one corner of the board. Let’s say you want to move it to a specific square to defend your queen. What’s the fewest number of moves it’ll take to get there?

This is a classic graph problem.

Each square on the chessboard can be represented as a node. If a knight can legally move from one square to another, there's an edge between them. The knight’s movement rules – those L-shaped hops – define the graph’s edges. So if you think about it, you're navigating a graph, trying to find the shortest path from one node (start square) to another (target square).

Let’s break it down.

Modeling the Board as a Graph

• The chessboard is an 8x8 grid.

• Each square is a node, identified by its coordinates (x, y) where 0 ≤ x < 8 and 0 ≤ y < 8.

• A knight has a maximum of 8 possible moves from any position (some may be out of bounds).

• The goal is to build a graph where each node connects to all valid knight moves from that square.

BFS or DFS? Choosing the Right Tool

There are two traversal methods we discussed earlier, Breadth-First Search (BFS) and Depth-First Search (DFS). So, which one should we use to solve the Knight’s Travails problem?

Let’s think about what would happen if we used DFS.

DFS goes as deep as it can along one path before backtracking. So, if you use DFS to move the knight, it might follow a long, winding sequence of valid moves that eventually leads to the destination, say, in 7 moves.

But that doesn’t mean it’s the shortest path. The optimal path could have reached the target in just 3 or 4 moves, but DFS wouldn’t find that unless it happens to explore that exact path first.

Even worse, DFS doesn’t guarantee you’ll find the shortest path unless you exhaustively search every possibility and compare them, which is slow and inefficient for this kind of problem.

Now, here’s why BFS is a better fit.

BFS explores all positions the knight can reach in 1 move, then all positions reachable in 2 moves, then 3 moves, and so on. As soon as it finds the destination square, you can be sure it got there using the fewest possible steps, because it explores all shorter paths before any longer ones.

In short:

• DFS might reach the destination eventually, but not efficiently, and not necessarily via the shortest path.

• BFS guarantees that the path it returns is the shortest in terms of the number of moves.

That’s why, for problems like this, where minimum steps are the goal, BFS is the go-to approach.

Implementing Knight’s Travails with BFS

To model the knight’s traversal across the board, we’ll use a class called Square. This class will help us track:

• The knight’s current position on the board (x_coord, y_coord)

• A reference to its parent square, so we can reconstruct the shortest path once the destination is reached

• Keep track of all valid next moves (its children), which represent the squares the knight can legally move to from the current position

Here’s the initial class:

from collections import deque

# Class to represent a square on the chessboard
class Square:
    def __init__(self, x_coord, y_coord, parent=None):
        self.x_coord = x_coord
        self.y_coord = y_coord
        self.parent = parent
        self.children = []

This setup is useful because we’re building a path tree: each move creates a child node, and we can trace our way back to the starting point using the parent.

How Does a Knight Move?

A knight in chess moves in an “L” shape, two steps in one direction and one step perpendicular to it. If the knight is at the center of an 8x8 chessboard, it can make up to 8 legal moves. These moves can be visualized as edges connecting one square (node) to others.

Here’s how we can represent and generate those moves:

from collections import deque

# Class to represent a square on the chessboard
class Square:
    def __init__(self, x_coord, y_coord, parent=None):
        self.x_coord = x_coord
        self.y_coord = y_coord
        self.parent = parent
        self.children = []

    def generate_legal_moves(self):
        # All 8 possible knight moves (in L-shape)
        row_moves = [-2, -1, 1, 2, 2, 1, -1, -2]
        col_moves = [1, 2, 2, 1, -1, -2, -2, -1]

        for dx, dy in zip(row_moves, col_moves):
            nx, ny = self.x_coord + dx, self.y_coord + dy

            # Only add valid board positions (0–7 for an 8x8 board)
            if 0 <= nx < 8 and 0 <= ny < 8:
                self.children.append(Square(nx, ny, self))

Finding the Shortest Path

Now that we have the Square class and the knight’s possible moves, we should implement BFS to find the shortest path from a starting square to a destination.

# BFS function to find the shortest path from start to end square
def knight_travails(start_coords, end_coords):
    # Initialize the BFS queue with the starting square
    start_x, start_y = start_coords
    queue = deque([Square(start_x, start_y)])
    # Set to track visited positions and prevent revisiting
    visited = set()
    end_coords = tuple(end_coords)

    while queue:
        current = queue.popleft()
        coords = (current.x_coord, current.y_coord)

        # If this square is the target, we've found the shortest path
        if coords == end_coords:
            return current

        # Skip, if this position has already been visited
        if coords in visited:
            continue

        visited.add(coords)

        # Generate all legal knight moves from the current square
        current.generate_legal_moves()
        # Append children to queue
        queue.extend(current.children)

def construct_path(start, end):
    # Run BFS to get the final square
    end_square = knight_travails(start, end)
    path = []

    # Trace back from the end square to the start using the parent links
    while end_square:
        path.append((end_square.x_coord, end_square.y_coord))
        end_square = end_square.parent

    # Reverse the path to show it from start to end
    return path[::-1]

Once you’ve implemented the functions above, you can print the output like this:

print(construct_path([3, 4], [0, 1]))

This returns the shortest sequence of moves the knight must take to travel from [3, 4] to [0, 1]. Sample output:

[(3, 4), (2, 2), (0, 1)]

Each tuple represents a square on the chessboard that the knight visits. This is the shortest possible path the knight can take (from start to end square) – and thanks to how BFS works, we know for sure that no shorter path exists. That guarantee of optimality is what makes Breadth-First Search a perfect fit here.

Wrapping Up

From chessboards to road maps and airline routes, graphs are everywhere. They silently power much of the technology we rely on daily. Whether you're booking a flight, navigating a city, or getting a recommendation on your favorite app, graphs are often at work behind the scenes.

They allow you to model and solve complex real-world problems by connecting entities and exploring their relationships. So next time your Google Maps reroutes you, remember: graphs are the mechanism behind that magic. Once you start recognizing graphs, you start seeing the hidden structure behind apps, systems, and even games you use every day.

In this article, we'll explore the concept of binary exponentiation, understand how it works, and implement it in code.

What is Binary Exponentiation?

Binary exponentiation is a method to compute \(a^n\) (a raised to the power of n) using only multiplications, instead of the naïve \(O(n)\) multiplications.

This significant improvement in efficiency makes it possible to calculate extremely large powers quickly, even when dealing with modular arithmetic.

How Binary Exponentiation Works

The key idea behind binary exponentiation is to break down the exponent into its binary representation and use the properties of exponents to simplify the calculation.

Let's break it down step by step:

1. Convert the exponent n to its binary representation.

2. Initialize the result as 1 and the base as a.

3. Iterate through each bit of the binary representation of n from right to left: (a). If the current bit is 1, multiply the result by the current base. (b). Square the base (multiply it by itself).

4. Return the final result.

For example, let's calculate \(3^{13}\):

1. Convert 13 to binary: \(13_{10} = 1101_2\)

2. Initialize result = 1, base = 3

3. Iterate through the bits:

   • Bit 1: result = \(1 *3 = 3\), base = \(3 *3 = 9\)

   • Bit 0: result = 3, base = \(9 * 9 = 81\)

   • Bit 1: result = \(3 *81 = 243\), base = \(81 *81 = 6561\)

   • Bit 1: result = \(243 * 6561 = 1,594,323\)

Thus, \(3^{13}=1,594,323.\)

Why Binary Exponentiation is Efficient

The efficiency of binary exponentiation comes from two main factors:

1. Reduced number of multiplications: Instead of performing n-1 multiplications as in the naïve approach, we only perform \(O(log n)\) multiplications. This is because we're essentially breaking down the problem into smaller subproblems based on the binary representation of the exponent.

2. Reuse of previous calculations: By squaring the base at each step, we're reusing the results of previous calculations, which significantly reduces the overall number of operations needed.

To illustrate this efficiency, consider calculating \(a^{1000000}\). The naïve approach would require 999,999 multiplications, while binary exponentiation would only require about 20 multiplications (as \(\log_2(1000000) \approx 20\)).

Algorithm Implementation

Let's implement the binary exponentiation algorithm in Python:

def binary_exponentiation(base, exponent):
    result = 1
    while exponent > 0:
        # If the current bit is 1, multiply the result by the current base
        if exponent & 1:
            result *= base
        # Square the base
        base *= base
        # Move to the next bit
        exponent >>= 1
    return result

# Example usage
print(binary_exponentiation(3, 13))  # Output: 1594323

Let's break down the algorithm:

1. We initialize result to 1, which is the identity for multiplication.

2. We use a while loop to iterate until the exponent becomes 0.

3. We check if the least significant bit of the exponent is 1 using the bitwise AND operator &. If it is, we multiply the result by the current base.

4. We square the base by multiplying it by itself.

5. We use the right shift operator >>= to move to the next bit of the exponent.

6. Finally, we return the result.

Time Complexity Analysis

The time complexity of binary exponentiation is \(O(log n)\), where n is the exponent. This is because:

1. The number of bits in the binary representation of n is \(\lfloor \log_2 n\rfloor + 1\).

2. We perform at most two multiplications per bit (one for squaring the base, and potentially one for updating the result).

Therefore, the total number of multiplications is at most \(2(\lfloor \log_2 n \rfloor + 1)\), which simplifies to \(O(\log n)\).

Example Problems and Solutions

Let's look at some algorithmic problems that you can solve efficiently using binary exponentiation, along with detailed explanations of the solutions and how we arrived at using binary exponentiation.

Problem 1: Modular Exponentiation

Problem: Calculate \(3^{1000000} \bmod 1000000007\).

Approach:

1. We recognize that this problem involves a very large exponent (1000000), which would be impractical to compute using naïve exponentiation.

2. We also notice that we need to find the result modulo a large prime number (1000000007).

3. This combination of a large exponent and modular arithmetic is a clear indicator that we should use modular binary exponentiation.

Solution: We'll modify our binary exponentiation function to include modular arithmetic:

def mod_binary_exponentiation(base, exponent, mod):
    result = 1
    base %= mod
    while exponent > 0:
        if exponent & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent >>= 1
    return result

print(mod_binary_exponentiation(3, 1000000, 1000000007))  # Output: 624098969

Explanation:

1. We initialize result to 1 and set base to base % mod to handle cases where the initial base is larger than the modulus.

2. The main loop works similarly to the original binary exponentiation algorithm, but with two key differences:

   a. When updating result, we perform (result * base) % mod. This ensures that result never exceeds mod, preventing integer overflow and maintaining the correct modular result.

   b. When squaring base, we perform (base * base) % mod for the same reason.

3. The bitwise operations (exponent & 1 and exponent >>= 1) work exactly as in the original algorithm, allowing us to process the binary representation of the exponent efficiently.

4. By applying the modulo operation at each step, we ensure that all intermediate results remain within the range [0, mod-1]. This is possible because of the properties of modular arithmetic:

   $$(a⋅b)modm=((amodm)⋅(bmodm))modm$$

This problem would be impossible to solve with naïve exponentiation due to the huge result, but modular binary exponentiation makes it tractable by keeping all intermediate results manageable.

Problem 2: Matrix Exponentiation

Problem: Given a 2x2 matrix A, calculate An where n = 1000000.

Approach:

1. We observe that we need to raise a matrix to a very large power (1000000).

2. Matrix multiplication is associative, which allows us to use the same principle as binary exponentiation for numbers.

3. We recognize that this is a perfect scenario for applying binary exponentiation to matrices.

Solution: We can use binary exponentiation on matrices. Here's a Python implementation with explanations:

import numpy as np

def matrix_multiply(A, B, mod):
    return np.array([[(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod, (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
                     [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod, (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod]])

def matrix_power(A, n, mod):
    result = np.eye(2, dtype=int)
    while n > 0:
        if n & 1:
            result = matrix_multiply(result, A, mod)
        A = matrix_multiply(A, A, mod)
        n >>= 1
    return result

A = np.array([[1, 1], [1, 0]])
n = 1000000
mod = 1000000007

result = matrix_power(A, n, mod)
print(result)  # Output: [[690749268 297612485]
                #         [297612485 393136783]]

Explanation:

1. matrix_multiply(A, B, mod):

   • This function performs matrix multiplication of two 2x2 matrices, A and B.

   • Each element of the resulting matrix is computed using the standard matrix multiplication formula, followed by a modulo operation to keep the values manageable.

2. matrix_power(A, n, mod):

   • This function implements binary exponentiation for matrices.

   • We start with result as the 2x2 identity matrix (created using np.eye(2, dtype=int)).

   • The main loop follows the same pattern as scalar binary exponentiation: a. If the current bit of n is 1, we multiply result by the current A. b. We square A (by multiplying it with itself). c. We right-shift n to move to the next bit.

   • All matrix multiplications are done using our matrix_multiply function, which incorporates modular arithmetic.

This matrix exponentiation technique is particularly powerful for solving linear recurrence relations in logarithmic time, as demonstrated here with the Fibonacci sequence.

Practice Problems

Here are some problems for you to solve using binary exponentiation:

1. Modular Exponentiation: Calculate \(7^{1234567} \bmod 1000000009\). (Hint: Use the mod_binary_exponentiation function from Problem 1 in the examples.)

2. Last Digit: Find the last digit of . (Hint: Observe the pattern of last digits of powers of 2 and use binary exponentiation with modulo 10.)

3. Power Tower: Calculate the last 3 digits of \(2^{2^{20}}\). (Hint: Use the property of modular arithmetic that \(a^b \bmod m = a^{b \bmod \phi(m)} \bmod m\) where \(\phi\) is Euler's totient function. You'll need to calculate \(2^{20} \bmod \phi(1000)\) first.)

4. Matrix Chains: Given a 2x2 matrix A = [[1, 2], [3, 4]], calculate the last two digits of the sum of all elements in \(A^{1000000}\). (Hint: Use matrix exponentiation as in Problem 2 from the examples, but only keep track of the last two digits of each element. You'll need to sum the elements after the final exponentiation.)

5. Fibonacci Sequence: Find the 1000000th Fibonacci number modulo 1000000007. (Hint: Use the matrix form of the Fibonacci sequence ([[1, 1], [1, 0]]) and apply matrix exponentiation as shown in Problem 2 of the examples.)

Conclusion

Binary exponentiation is a powerful technique that can be applied to a wide range of problems involving large exponents. As we've seen in the example and practice problems, it's particularly useful in modular arithmetic, matrix operations, and solving recurrence relations.

By practicing these problems, you'll gain a deeper understanding of how to apply binary exponentiation in various scenarios. Remember, the key is to recognize when a problem involves raising something to a large power, whether it's a number, a matrix, or even a more complex structure.

If you found this explanation of Binary Exponentiation algorithm helpful, you might also enjoy more in-depth programming tutorials and concepts I cover on my blog.

We just posted a course on the freeCodeCamp.org YouTube channel that will help you master the stack data structure. The course is a deep dive into one of the most fundamental and powerful data structures in computer science. Parth from Destination FAANG developed this course.

Stacks are dynamic data structures that follow the Last In, First Out (LIFO) principle, where the last element added to the stack is the first one to be removed. This course, enriched with diagrams and code examples, will provide you with a solid understanding of stacks and prepare you to ace those crucial interview questions.

Here are the sections in the coruse:

Introduction to Stacks

The course begins with an introduction to the stack data structure, explaining its LIFO nature and its analogy to a stack of plates. You'll learn about the basic operations of push (adding an item to the top), pop (removing the top item), and peek (viewing the top item without removing it), illustrated with Java examples:

Stack<Integer> stack = new Stack<>();
stack.push(10); // Pushes 10 on the stack
stack.push(20); // Pushes 20 on the stack
stack.pop();    // Removes the top item (20)
int top = stack.peek(); // Returns 10 without removing it

Implementation, Operations, and Use Cases

This section covers the internal workings of stacks, showcasing how to implement a stack in Java using arrays or linked lists. You'll explore advanced stack operations and delve into practical use cases, such as undo mechanisms in text editors, parsing expressions, and backtracking algorithms.

When to Use Stacks

Understanding when and where to apply stacks is crucial. This part of the course will guide you through scenarios where stacks shine, including function call management, syntax parsing, and maintaining histories in applications.

Ace Your Interviews with These Stack Questions

The course includes a dedicated section to prepare you for interviews, focusing on the 10 most popular stack-related questions. Each problem is broken down, explained, and solved with Java code to enhance your problem-solving skills and stack understanding.

1. Daily Temperatures: Learn how to use a stack to find the number of days until a warmer temperature.
2. Evaluate Reverse Polish Notation: Decode and evaluate expressions in Reverse Polish Notation using stacks.
3. Valid Parentheses: Use a stack to check for the validity of parentheses in a string.
4. Min Stack: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
5. Generate Parentheses: Discover how to generate all combinations of well-formed parentheses with stacks.
6. Car Fleet: Understand how to apply stacks to solve complex problems like the car fleet challenge.
7. Minimum Remove to Make Valid Parentheses: Use stacks to balance parentheses in a string efficiently.
8. Largest Rectangle in Histogram: Tackle this classic problem with a stack-based approach to find the largest rectangular area.
9. Longest Valid Parentheses: Learn to use stacks to find the length of the longest valid parentheses substring.
10. Max Stack: Design a max stack that supports all regular stack operations along with retrieving the stack's maximum element.

Your Path to Stack Mastery

By the end of this course, you'll have a deep understanding of stacks, equipped with the knowledge to implement and utilize them effectively in various scenarios. Whether you're preparing for an interview or looking to solidify your understanding of data structures, this course offers a comprehensive guide to mastering stacks with real-world applications and interview-ready questions.

Watch the full course on the freeCodeCamp.org YouTube channel (3-hour watch).

Nodes are connected through references, forming the linked structure. One advantage of linked lists is that insertion and deletion of elements at the beginning of the list can be done in constant time, denoted as O(1).

This efficiency stems from the ability to directly manipulate references without needing to shift elements as required in arrays. Data types in a linked list can be any of the available data types supported by a programming language.

In this tutorial, you'll learn the following:

• Understanding Linked list
• Types of Linked List
• Summary of operations with their respective time and space complexities in tabular format.
• Differences Between Array and Linked list.
• Algorithm: Solve the Remove Duplicates from Sorted list in PHP and JavaScript.

Understanding Linked list

head => Points to the first box in the list
tail => Points to the last box in the list

To access the data in the first box

head.data => 6

To access the data in the second box, we first need to set the pointer (arrow) to point to the box. Hence we need the (next)
head.next => This points to the next item on the list
head.next.data => 4

To access the data in the third box, we first need to set the pointer (arrow) to point to the box. Hence we need the (next.next)
head.next.next => This points to the next > next item on the list
head.next.next.data => 5

What is a node ?

A node in a linked list is an example of a self-referential structure in programming. This structure is comprised of elements called nodes, where each node contains both data and a reference to another node of the same type. This reference, often termed a 'pointer,' facilitates the creation of a chain-like structure, where nodes are interconnected, forming the linked list.

The self-referential nature of nodes allows for efficient traversal and manipulation of data within the linked list. The structure can be implemented using classes or arrays

How to Implement a Linked List Using classes

class Node {
    public function __construct(
        public $data,
        public ?Node $next = null
    ) {}
}

// Creating nodes

$node1 = new Node(10);
$node2 = new Node(20);
$node3 = new Node(30);

// Linking nodes

$node1->next = $node2;
$node2->next = $node3;

// Traversing linked list

$current = $node1;
while ($current != null) {
    echo $current->data . " ";
    $current = $current->next;
}

How to Implement a Linked List Using Using arrays

// creating nodes as an associative array

$node1 = ['data' => 10, 'next' => null];
$node2 = ['data' => 20, 'next' => null];
$node3 = ['data' => 30, 'next' => null];

// linking nodes

$node1['next'] = &$node2;
$node2['next'] = &$node3;

// Traversing linked list

$current = $node1;
while ($current != null) {
  echo $current["data"] . " ";
  $current = &$current["next"];
}

In both cases, we create a structure where each element (node) contains data and a reference (next) to another element of the same type. This creates a self-referential structure. We then link these elements together to form a data structure like a linked list. Finally, we traverse the structure to access and manipulate its elements.

Unlike an array, a linked list doesn't provide constant time access to a particular index within the list. This means that if you'd like to find the nth element in the list, you'll need to traverse through to the nth element.

Traversing a linked list means iterating through each node of the list until the end node is reached.

Types of Linked list

We'll discuss the types under the Traversal, Memory and Complexity categories.

Singly Linked List

Each node has data and a reference to the next node.

Non-code explanation

Imagine taking a journey by train, where each train represents a part of your trip, and each station represents a point where you need to make a change.

• Train A represents the first part of your journey, taking you from Station A to Station B. When you arrive at Station B, there's a sign directing you to switch trains to continue your journey.
• Train B represents the second part of your journey, taking you from Station B to Station C. Again, when you arrive at Station C, there's no sign for another train because you've reached your final destination.

In this analogy:

• Each train segment (Train A, Train B, and Train C) represent a node in the singly linked list.
• The task of each train is analogous to the data stored in each node, representing a segment of your journey.
• The transition between trains at each station is analogous to the "next" pointer in a linked list, indicating the next segment of your journey.
• At the final destination (Station C), there's no need for a pointer or sign to another train because it's the end of your journey.

In simpler terms, a singly linked list is like a train journey with different segments, where each train (node) has the task of taking you from one station to the next until you reach your final destination. The transitions between trains are like pointers, guiding you through each segment of your journey.

Performance Characteristics of Singly Linked List

1. Traversal: Traversal is allowed only in one direction (that is, forward only). You can move forward through the list, but you cannot easily move backward.
2. Memory Efficiency: Singly linked list is generally more memory-efficient because it requires only one reference per node.
3. Complexity: Insertion and Deletion operation is easier as you only need to update references in one direction.

Time and Space Complexity

I wrote about constant and linear time complexity here, and we'll be using that to discuss the general time and space complexities for some common operations:

Traversal

Time complexity O(n), where n is the number of nodes in the list. Space complexity O(1), it doesn't require additional space proportional to the input size.

Insertion at the Beginning

Time complexity O(1), it involves updating references at the head. Space complexity O(1), it doesn't require additional space proportional to the input size.

Insertion at the End

Time complexity O(n), it may require traversing the entire list to reach the end. Space complexity O(1), it doesn't require additional space proportional to the input size.

Deletion at the Beginning

Time complexity O(1), it involves updating references at the head. Space complexity O(1), constant.

Deletion at the End

Time complexity O(n), it may require traversing the entire list to reach the end. Space complexity O(1), constant.

Doubly Linked List

In a doubly linked list, the head node typically does not have a prev reference because it is the first node and therefore has no previous node.

However, the head node does have a next reference pointing to the next node in the list. Each node has data and references to both the next and previous nodes.

Non-code explanation

Imagine that you have a book where each page represents a task you need to complete, just like items on your to-do list.

Each page does not only contain information about the task written on it but also has connections to the pages before and after it in the book.

• Page 1 (Task A) represents the first task in the book. It contains information about Task A and has an arrow pointing forward to Page 2 (Task B), indicating that Task B comes after Task A in the book. However, Page 1 does not have a backward arrow because it is the first page of the book and doesn't have a previous page.
• Page 2 (Task B) contains information about Task B and has arrows pointing both forward to Page 3 (Task C) and backward to Page 1 (Task A), indicating that Task C comes after Task B and Task A comes before Task B in the book.
• Page 3 (Task C) represents the last task in the book. It contains information about Task C and has an arrow pointing backward to Page 2 (Task B), indicating that Task B comes before Task C in the book.

With this in mind, you can think of a doubly linked list as a book where each page not only contains information about a task but also provides easy navigation to the tasks before and after it. The first page, similar to the head of a doubly linked list, does not have a previous reference, while the last page, similar to the tail of a doubly linked list, does not have a next reference

Performance Characteristics of Doubly Linked Lists

1. Traversal: Doubly linked lists allow traversal in both directions — forward and backward. This bidirectional traversal enables more flexible navigation through the list, allowing operations such as iterating in reverse order.
2. Memory Efficiency: Doubly linked lists typically require more memory compared to singly linked lists because each node contains two references (pointers) — one for the next node and one for the previous node. This additional memory overhead per node can impact the overall memory efficiency, especially for large lists.
3. Complexity: Doubly linked lists offer bidirectional traversal and flexibility. Insertion and deletion operations may require updating references in both directions (forward and backward), which can increase the complexity and potentially impact performance.

Time and Space Complexity

Traversal

The time and space complexity for this operation is the same with the singly linked list.

Insertion at the Beginning

The time and space complexity for this operation is the same with the singly linked list.

Insertion at the End

Time complexity for this operation takes O(1) time. This is because you have direct access to the tail node, so you can update the references without needing to traverse the entire list. Space complexity O(1), it doesn't require additional space proportional to the input size.

Deletion at the Beginning

The time and space complexity for this operation is the same with the singly linked list.

Deletion at the End

Time complexity for this operation takes O(1) time. This is because you have direct access to the tail node, so you can update the references without needing to traverse the entire list. Space complexity O(1), it doesn't require additional space proportional to the input size.

Circular Linked List

A circular linked list is a type of linked list where the last node of the list points back to the first node, forming a circle or loop. This characteristic distinguishes it from a traditional linked list, where the last node typically points to null, indicating the end of the list. In a circular linked list, there is no null pointer at the end; instead, the last node points back to the first node, creating a loop structure. This looping behavior allows for continuous traversal through the list. The below image shows how a singly circular linked list works.

Non-code explanation

Imagine a train line that forms a loop, with passengers boarding and exiting at various stations along the way. This loop represents a circular linked list, where each station is a node and the train continuously travels around the loop, picking up and dropping off passengers.

Just like in a circular linked list, the loop ensures continuous traversal without an end point, and passengers (data) can be added or removed at any station (node).

The circular linked list offers advantages in certain applications but requires careful handling of pointers and memory management to maintain its circular structure and prevent issues such as infinite loops.

Performance Characteristics of Circular Linked Lists

1. Traversal: Circular linked lists enable traversal in a loop, allowing seamless navigation from one node to another regardless of the direction. This circular structure facilitates efficient traversal without needing to iterate back to the beginning when reaching the end, enhancing traversal performance.
2. Memory Efficiency: Singly circular linked lists typically offer similar memory efficiency to singly linked lists, as they require only one pointer per node to connect to the next node in the sequence. This single-pointer structure results in lower memory overhead per node compared to doubly linked lists, potentially improving memory efficiency for large lists.
3. Complexity: In singly circular linked lists, insertion and deletion operations require updating references to maintain the circular structure, introducing moderate complexity compared to linear linked lists.

Time and Space Complexity

Traversal

Time Complexity: O(n) – Since you have to traverse through all the nodes in the list to reach the end.

Space Complexity: O(1) – Only a constant amount of extra space is required for a temporary variable to traverse the list.

Insertion at the Beginning

Time Complexity: O(1) – Insertion at the beginning simply involves updating the references at the head.

Space Complexity: O(1) – No additional space is required.

Insertion at the End

Time Complexity: O(n) – It may require traversing the entire list to reach the end where insertion needs to take place.

Space Complexity: O(1) – No additional space is required.

Deletion at the Beginning

Time complexity O(1), it involves updating references at the head.

Space complexity O(1), constant.

Deletion at the End

Time complexity O(n), it may require traversing the entire list to reach the end.

Space complexity O(1), constant.

Summary of Operations for the Time Complexity

Summary of Operations for the Space Complexity

Differences Between Array and Linked list

A linked list is a dynamic way to represent a list, where adding and removing items from the beginning of the list typically involves changing only a few pointers. This operation can be performed in constant time, denoted as O(1), regardless of the list's size.

On the other hand, arrays are a sequential representation of a list. Adding or removing items from the beginning of the list requires shifting all subsequent elements to accommodate the change. This operation has a time complexity of O(n), where n is the number of elements in the array. Therefore, for large arrays, adding or removing items from the beginning can be relatively slow compared to linked lists.

How to Solve the Remove Duplicates from Sorted List Problem

Explanation of the problem: Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Solution in PHP

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */


class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function deleteDuplicates($head) {
        $node = $head;

        while($node !== null && $node->next !== null) {

            if ($node->val == $node->next->val) {
                $node->next = $node->next->next;
            }else {
                $node = $node->next;
            }   
        }

        return $head;
    }
}

Solution in JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */


var deleteDuplicates = function(head) {
    let node = head;

    while(node?.next) {

        if (node.val === node.next.val) {
            node.next = node.next.next
        } else {
            node = node.next
        }
    }

    return head
};

Code explanation

Given the deleteDuplicates method:

• node is initialized to the head of the linked list.
• A while loop iterates through the linked list until the end or until the current node's next property is null.
• Inside the loop, it checks if the current node's value is equal to the next node's value. If they are equal, it skips the next node by setting the current node's next property to the next node's next property.
• If the values are not equal, it moves to the next node by updating the value of node to node->next.
• Finally, the method returns the head of the modified linked list.

The null safe operator (?.) used in the JS code solution is also available from PHP 8.0.

This code efficiently removes duplicates from a singly-linked list by adjusting pointers and has a time complexity of _O_(_n_) and a space complexity of _O_(1), where n is the number of nodes in the linked list.

Reference

• How does a linked list work

Conclusion

In this article, you learned about linked list, types of linked list and a real world problem that involves solving the removal of duplicates from sorted list.

Keep learning, and Happy Coding!

You can find me on LinkedIn and Twitter.

We just posted a course on the freeCodeCamp.org YouTube channel that will equip you with the knowledge to excel in coding interviews and problem-solving. You will learn the important data structures and algorithms you need to know to develop efficient code.

Course Overview

The course is designed to cover the breadth and depth of topics necessary for placement preparations, coding interviews, and enhancing logical thinking capabilities. With a focus on real-world applications, the course ensures learners are not just memorizing code but truly understanding the principles behind the solutions. It walks you through various Java algorithms and data structure problems, accompanied by step-by-step visualizations to foster genuine learning.

Java, known for its versatility and widespread use, is the primary language used in this course. However, students with backgrounds in other programming languages like Javascript, Python, C#, C++, or C can also easily grasp the concepts taught. The course uniquely utilizes animated slides to demonstrate the implementation of various algorithms and data structures, making complex topics accessible and engaging.

What You Will Learn

This comprehensive course covers a wide array of topics to prepare you for technical interviews and software development challenges, including:

• Algorithm Analysis: Understanding the efficiency and scalability of algorithms.

• Data Structures: Diving into arrays, matrices, linked lists (singly, doubly, and circular), stacks, queues, binary trees, binary search trees, graphs, priority queues, heaps, and the Trie data structure.

• Core Concepts: Exploring recursion, searching, sorting, strings, and dynamic programming.

Each section is crafted to address common interview questions and scenarios, ensuring learners are well-prepared for the questions they might face in an actual interview setting.

Why Choose This Course?

• Real-World Problem Solving: Learn how to approach and solve complex problems with optimal solutions.

• Visual Learning: Animated slides and step-by-step visualizations make learning interactive and effective.

• Comprehensive Coverage: From basic to advanced topics, this course has everything covered.

• Language Versatility: While Java is used, concepts are applicable across various programming languages.

• Interview Preparation: Specifically designed to tackle the most common interview challenges in the IT industry.

Conclusion

Whether you're aiming to land a software engineering job or simply wish to deepen your understanding of data structures and algorithms, this course is for you. Watch the full course on the freeCodeCamp.org YouTube channel (48-hour watch).

In this tutorial, you'll learn the following:

• Constant and linear time complexity.
• Why use a hash map?
• Things to consider when writing hash functions.
• How to solve the Two Sum problem in PHP and JavaScript.

What is Constant Time Complexity - O(1)?

O(1) indicates that the running time of an algorithm is constant, regardless of the input size.

This implies that the algorithm's performance isn't dependent on the size of the input. An example is accessing an index of an array.

<?php

function constantTimeAlgorithm($arr) 
{

    echo $arr[0] . PHP_EOL;
}

Here is a non-code example to illustrate the concept of constant time complexity:

Imagine sending a file through an airline to your friend, and the airline has a policy where they charge based on the weight of the package.

Now, whether your file weighs 2 grams or 20 kilograms, the airline's processing time remains constant. This means that the time it takes for the airline to handle your package doesn't depend on the weight of the file – it's always the same.

In other words, the processing time is constant irrespective of the size of the file.

What is Linear Time Complexity - O(n)?

O(n) indicates that the running time of an algorithm grows linearly with the size of the input.

The performance of the algorithm is directly proportional to the input size. An example is traversing a for loop and printing elements.

<?php

function linearTimeAlgorithm($arr) 
{
    foreach ($arr as $element) {
        echo $element . PHP_EOL;
    }
}

Here's a non-code example to illustrate the concept of linear time complexity:

Consider using an electronic transfer service to send a file to your friend. In this scenario, the time it takes to transfer the file increases linearly with the size of the file.

For instance, if it takes 1 minutes to transfer a 100 MB file, it would take approximately 100 minutes to transfer a 10 GB file using the same service.

This linear relationship between the size of the file and the time it takes to transfer it reflects linear time complexity. The time taken to transfer the file increases proportionally or linearly with the size of the input or file.

Why use a Hash Map?

Illustration of how a hash map works

A hash map is a concrete implementation of the abstract data type known as an associative array.

In a hash map, keys are hashed to determine the index where the corresponding values will be stored, allowing for efficient retrieval and storage of key-value pairs.

This implementation typically provides fast access times for operations like insertion, deletion, and lookup of values based on their associated keys.

In languages like PHP or JavaScript, when you use an associative array, you are essentially using a hash map. Their associative arrays are implemented using hash tables behind the scenes.

You can use strings, integers, or other data types as keys, and the language's internal hashing mechanism efficiently maps these keys to their corresponding values. Additionally, JavaScript provides the Map object for more advanced hash map functionalities.

Time and Space Complexity for Hash Map

The time and space complexity for a hash map (or hash table) is not necessarily O(n) for all operations. The typical and desired time complexity for basic operations like insertion, lookup, and deletion in a well-designed hash map is O(1) on average.

Here's a breakdown of time and space complexity for a hash map:

Time Complexity:

Average Case:

• Insertion (average): O(1)
• Lookup (average): O(1)
• Deletion (average): O(1)

Worst Case:

• Insertion (worst): O(n), where n is the size of the hash map. This occurs when there are many hash collisions, leading to linear probing or other collision resolution strategies that may involve traversing the entire hash map.
• Lookup and Deletion (worst): O(n), for the same reason as insertion.

Space Complexity:

• The space complexity is typically O(n). Where n is the number of key-value pairs stored in the hash map. Each key-value pair occupies constant space, and the space required grows linearly with the number of elements.

In algorithm analysis, the notation O(1) and O(n) represent the upper bounds on the time complexity of an algorithm, where n is the size of the input.

Operations

1. Insertion: The key-value pair is hashed, and the resulting index is used to store the value in the corresponding slot. If a collision occurs, the collision resolution strategy is applied.
2. Deletion: The key is hashed to find the index, and the item at that index is removed. Collision resolution may be necessary.
3. Lookup: The key is hashed to find the index, and the value at that index is returned. Collision resolution may be applied if needed.

Things to consider When Creating Hash Tables

When creating hash tables, there are several important considerations to ensure efficiency, including fast computation of hash codes and effective collision resolution strategies.

Fast Computation

Hash codes should be computed quickly to ensure efficient insertion, lookup, and deletion operations. A good hash function contributes to the speed of hash code computation.

Avoid collision

A collision happens when two or more keys produce the same hash code. In other words, multiple keys map to the same array index.

How to Handle Collisions

Hash maps use collision resolution techniques to deal with collisions. Common strategies include:

Chaining

To manage several values with the same hash code, chaining involves storing a linked list or other data structure at each array index. If a collision occurs, the new key-value pair is appended to the linked list at the relevant index.

Open addressing

When a collision happens in a hash table, a technique called open addressing is employed to resolve it by searching for the next open space.

All it does is search the array for the next empty slot where the key-value combination can be placed. Methods including double hashing, quadratic probing, and linear probing are applied.

Linear Probing: In linear probing, the algorithm moves linearly to the next index in the array in order to find the next open slot when a collision occurs.

Quadratic Probing: In this method, an algorithm employs a quadratic function to find the next slot that becomes available.

Double Hashing: In double hashing, the algorithm calculates the step size between probes using a secondary hash function.

In order to reduce the possibility of collisions, a good hash function should generate distinct hash codes for various inputs. By making sure the hash codes are evenly distributed throughout the range of potential values, collisions can be prevented.

How to Solve the Two Sum Problem

Two sum problem

The Two Sum problem involves finding all pairs of elements in an array that sum up to a specific target value. Now let's look at the problem statement.

Problem statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Example 1:

Input: nums = [3,2,4, 8], target = 12

Output: [2, 3]

Example 2:

Input: nums = [5,5], target = 10

Output: [0,1]

Solution

To solve the Two Sum problem, we can use a hash table. The idea is to traverse the nums array and, for each element, check if the complement (the difference between the target and the current element) is already in the hash table. If it is, we have found a pair of indices whose elements add up to the target.

Here are the steps to follow:

1. To hold the elements and their respective indices, create an empty hash table upon initialization.
2. Go over the array of nums.
3. Do the complement calculation (target - current element) for each element.
4. Verify if the complement has already been added to the hash table. If yes, return the current index and the index stored in the hash table for the complement.
5. If the complement is not in the hash table, store the current element and its index in the hash table.
6. If no such pair is found during the traversal, it implies that there is no solution.

PHP Code Solution

<?php

function twoSum($nums, $target) {
    $hashTable = [];

    foreach ($nums as $i => $num) {
        $complement = $target - $num;

        if (array_key_exists($complement, $hashTable)) {

            // Found the pair, return the indices
            return [$hashTable[$complement], $i];
        }

        // Store the current element in the hash table
        $hashTable[$num] = $i;
    }

    // No solution found
    return [];
}

// Example usage:
$nums = [2, 7, 11, 5, 15, 30];
$target = 12;
$result = twoSum($nums, $target);

echo "Indices of the two numbers: [" . implode(", ", $result) . "]";

JavaScript Code Solution using map Function

function twoSum(nums, target) {
    const hashTable = new Map();

    for (const [index, num] of nums.entries()) {
        const complement = target - num;

        // Check if the complement is in the Map
        if (hashTable.has(complement)) {

            // Found the pair, return the indices
            return [hashTable.get(complement), index];
        }

        // Store the current number and its index in the Map
        hashTable.set(num, index);
    }

    // No solution found
    return [];
}

// Example usage:
const nums = [2, 7, 11, 5, 15, 30];
const target = 12;
const result = twoSum(nums, target);

console.log(`Indices of the two numbers that add up to ${target}: [${result.join(', ')}]`);

This approach has a time complexity of O(n) because we iterate through the array once. The space complexity is also O(n) due to the storage of elements in the hash map.

Resources

1. Hash table From Wikipedia
2. Hash maps in Python

Conclusion

In this article, you learned about hash maps, things to consider when writing hash functions and a real world problem that involves solving the Two Sum problem.

Keep learning, and Happy Coding!

You can find me on LinkedIn and Twitter.

During this process, I came across the Sliding Window technique. I found this algorithm to be very interesting, so I wanted to share my learnings with the community.

This tutorial will be useful for you if you're preparing for competitive programming interviews. So, let's get started.

What is the Sliding Window Technique?

The sliding window technique is an algorithmic approach used in computer science and signal processing. It involves selecting a fixed-size subset, or "window," from a larger dataset and moving this window through the dataset in a step-wise fashion.

The window slides over the data, typically one element at a time, and performs some operation on the elements within the window at each step.

Are you confused? Let me elaborate on this technique with an example.

Sliding Window example

Assume you're practicing for competitive programming and you encounter the following problem:

"Find the maximum sum of sub-array of size k with the time complexity of O(N).

Array = [1, 2, 6, 2, 4, 1], k = 3"

If you're not familiar with the concept of time complexity, here's a quick definition:

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.

And here's a course if you'd like to learn more.

Back to our problem. Basically, we have to find the sub-array of size 3, whose sum is the maximum (largest number). Here's a pictorial view of how we can go about solving this:

Find sum of sub-array of size k

Manual solution

Let's solve it manually. From the above image, let's find the sum of each of the sub-arrays of size 3.

• Sum of 1st sub-array = 1 + 2 + 6 = 9
• Sum of 2nd sub-array = 2 + 6 + 2 = 10
• Sum of 3rd sub-array = 6 + 2 + 4 = 12
• Sum of 4th sub-array = 2 + 4 + 1 = 7

The maximum (biggest) number among 9, 10, 12, and 7 is 12 – or the 3rd sub-array. That is our solution.

Code solution

Alright, let's wear our programming shoes and try to solve this using code.

Here's my solution to the problem:

Here's a quick walk through of the above code.

I'm defining the input array and window size at the bottom, and calling the method findMaxSumOfSequence with these parameters.

Initially I'm doing a validation if the input array size is more than the window size, else the calculation is not possible, so return null.

I'm assuming the maximum sum to be negative infinity.

I iterate over the array, and for each item in the array, I iterate for next k items, find their sum, and assign the current window sum to maximum sum variable if the current window sum is more than existing maximum sum. Finally, return the maximum sum.

Let's try to run the code.

Find maximum sum of a sub-array of size k

Here we go. We got the right answer.

But, the problem does not stop here. If you look at the problem carefully, we have to find the solution in O(N) time complexity.

So, you might wonder what's the time complexity of the above solution. Well, the time complexity of the above solution is O(N*k). This means, we're iterating k times for each item in the array (nested for-loop).

O(N) time complexity basically describes that you have to find the maximum value by iterating over the given array only once.

Using the Sliding Window technique

How do we solve this with one iteration? Here's where sliding window technique comes into play. Let's take a look at the pictorial representation of our solution once again:

Sliding window technique

Here, you may notice that the window slides over the array. It's initially covering the indices 0, 1, and 2 in the 1st sub-array. For the next sub-array, it slides one-position to the right, eliminating 0th index to the left and adding the 3rd index to the right. So, now it covers the 1, 2, and 3 in the 2nd sub-array...and so on.

The calculation goes this way for the sub-arrays:

• 1st sub-array = 1 + 2 + 6 = 9
• 2nd sub-array = 9 (sum of 1st sub-array) - 1 + 2 = 10

Let's take a look at this carefully. We find the sum of 1st sub-array to be 9. To calculate the sum of 2nd sub-array, we subtract the number that's going out (1 at 0th index) and add the number that's coming in (2 at 3rd index).

• 3rd sub-array = 10 (sum of 2nd sub-array) - 2 + 4 = 12
• 4th sub-array = 12 (sum of 3rd sub-array) - 6 + 1 = 7

This is the sliding window technique. Following this technique, we'll able to find the sum of maximum sub-array in a single iteration.

How to implement Sliding Window in code

Alright, let's put on our coding shoes again and try to implement this.

Let's try to understand the above code. I made some changes to the findMaxSumOfSequence method. I introduced start and end variables which describe the window block.

In this implementation, we have 2 loops but they're not nested. This is because, in the first loop, we have to find the sum of the 1st window. The second loop will subtract and add items from the result of the first loop.

From the above example, the first loop will iterate over the first k items (3) which are 1, 2, and 6. I calculate the sum and store them in the maxSum and windowSum variables.

In the next loop, I'm iterating over each item in the array. For each item, I'm subtracting the previous number and adding the next number, and updating the result in the windowSum variable. I compare the windowSum and maxSum variables and update the maxSum variable if the windowSum is larger. Then I move the window to the next sub-array by incrementing the start and end variables. Finally, I return the maximum sum.

Here's the output of the above code:

Find maximum sum of a sub-array of size k using sliding window technique

With this implementation, we have satisfied the problem's requirement by iterating over the array only once and finding the maximum sum of a sub-array (with O(N) time complexity).

Applications of the Sliding Window Technique

The Sliding Window Technique is versatile and finds applications in various domains.

Array and String Manipulation: In array or string processing, a sliding window can be used to efficiently perform operations such as finding subarrays or substrings that satisfy certain conditions.

Data Compression: Sliding window compression algorithms, like LZ77 and its variants, use a window to find repeated patterns in the input data and replace them with references to previous occurrences.

Image Processing: In image processing, a sliding window can be employed for tasks such as feature extraction, object detection, or image segmentation.

Signal Processing: Time-series data can be analyzed using a sliding window to capture local patterns, trends, or anomalies.

Network Protocols: Sliding window protocols are used in computer networks for reliable and efficient data transmission. The sender and receiver maintain a window of allowable sequence numbers to manage the flow of data.

Conclusion

Hope you now have a clear idea of how the Sliding Window Technique works after seeing these examples. I would recommend that you try to solve some other problems with this technique to get familiar with it. Trying to find the minimum sum of the sub-array of size k on your own using this technique would be a helpful exercise.

As I mentioned earlier, I'm actively looking to switch my job. If you have a good position available in your organization, please refer me.

Hope you enjoyed reading this article. If you wish to learn more about techniques to crack competitive programming interviews, subscribe to my newsletter by visiting my site which also has a consolidated list of all my blogs.

Whether you’re a novice coder or an experienced developer, this handbook is your concise guide to the critical skill of data management through data structures.

Data today isn’t just vast – it’s also complex. Organizing, retrieving, and manipulating this data efficiently is key. Enter data structures — the backbone of effective data management.

This guide cuts through the complexity of arrays, linked lists, stacks, queues, trees, and graphs. You’ll gain insights into each type’s strengths, limitations, and practical applications, backed by real-world examples.

Even the big brains at places like MIT and Stanford say knowing your data structures is super important for making great software. And here, I'll share real-life case studies showing you how these data structures are used in everyday situations.

Ready to dive in? We're going to explore the world of data structures together. You'll find out how to make your data work smarter, not harder, and give yourself an edge in the tech world.

Here’s the awesome journey you’re about to embark on:

1. Land Your Dream Tech Job: Imagine walking into big names like Google or Apple with confidence. Your new skills in data structures could be your golden ticket to these tech havens, where knowing your stuff really matters.
2. Make Shopping Online a Breeze: Ever wonder how Amazon makes shopping so smooth? With your skills, you could be the wizard behind faster, smarter shopping experiences.
3. Be a Financial Whiz: Banks and finance companies love quick, error-free data handling. Your know-how could make you a star in places like Visa or PayPal, keeping money moving swiftly and safely.
4. Revolutionize Healthcare: In the world of health, like at Mayo Clinic or Pfizer, your ability to manage data could speed up lifesaving decisions. You could be part of a team that’s changing lives every day.
5. Level Up Gaming Experiences: Got a passion for gaming? Companies like Nintendo or Riot Games are always on the lookout for talent that can make games even more thrilling. That could be you.
6. Transform Shipping and Travel: Imagine helping FedEx or Delta Airlines move things faster and smarter around the globe.
7. Shape the Future with AI: Dream of working with Generative AI? Your understanding of data structures is crucial. You could be part of groundbreaking work at places like OpenAI, Google, Netflix, Tesla or SpaceX, making the stuff of science fiction real.

Upon completing this journey, your grasp of data structures will extend far beyond mere understanding. You'll be equipped to apply them effectively.

Imagine enhancing app performance, devising solutions for business challenges, or even playing a role in pioneering tech advancements. Your newfound skills will open doors to diverse opportunities, positioning you as a go-to problem solver.

Table Of Contents

1. The Importance of Data Structures
2. Types of Data Structures
3. Array Data Structure
4. Single-linked List Data Structure
5. Double-linked List Data Structure
6. Stack Data Structure
7. Queue Data Structure
8. Tree Data Structure
9. Graph Data Structure
10. Hash Table Data Structure
11. How to Unleash the Power of Data Structures in Programming
12. How to Choose the Right Data Structure for Your Application
13. How to Efficiently Implement Data Structures
14. Common Data Structure Operations and Their Time Complexities
15. Real-World Examples of Data Structures in Action
16. Resources and Tools for Learning Data Structures
17. Conclusion and Next Steps

Abstract digital cityscape with interconnected cubic structures and glowing lines symbolizing complex data structures - Source: lunartech.ai

1. The Importance of Data Structures

Learning about data structures can really help you power-up your software engineering skills. These critical components are key to ensuring your applications operate flawlessly, which is a must-have ability for every software engineer.

They Enhance Efficiency and Performance

Data structures are the turbochargers of your code. They do more than just store data – they enable swift and efficient access. Think of a hash table as your instant-access tool for speedy data retrieval or the linked list as your dynamic, adaptable strategy for evolving data needs.

They Optimize Memory Use and Management

These structures are really good at optimizing memory. They fine-tune your program’s memory consumption, ensuring robustness under heavy data loads and helping you avoid common issues like memory leaks.

They Boost Problem-Solving and Algorithm Design

Data structures elevate your code from functional to exceptional. They efficiently organize data and operations, enhancing your code’s effectiveness, reusability, and scalability. This leads to better maintainability and adaptability of your software.

They're Essential for Professional Advancement

Grasping data structures is crucial for any aspiring software engineer. Not only do they provide efficient ways to handle data and bolster performance, but they are also instrumental in solving complex problems and designing algorithms.

These skills are vital for career growth, particularly for those aiming to move into senior technical roles. Tech giants like Google, Amazon, and Microsoft value this expertise highly.

Key take-aways

Thoroughly learning data structures can help you stand out in technical interviews and attract leading employers. You'll also use them every day as a developer.

Data Structures are essential for building scalable systems and tackling intricate coding problems, and they're key to maintaining a competitive edge in the evolving tech sector.

This guide focuses on crucial data structures, empowering you to create efficient, advanced software solutions. Begin your journey to enhance your technical capabilities for future industry challenges.

2. Types of Data Structures

Data structures are essential tools in software development that enable efficient storage, organization, and manipulation of data. Understanding the different types of data structures is crucial for aspiring software engineers, as it helps them choose the most appropriate structure for their specific needs.

Let’s dive into some of the most commonly used types of data structures:

Arrays: The Backbone of Efficient Data Management

Arrays, a cornerstone of data structures, epitomize efficiency by storing elements of the same type in contiguous memory slots. Their power lies in their ability to offer direct, lightning-fast access to any element, simply by knowing its index.

This feature, according to a Stanford University study, makes arrays up to 30% faster for random access compared to other structures.

But arrays have their limitations: their size is fixed, and altering their length, particularly for large arrays, can be a resource-intensive task.

Illustration of an array. Source: lunartech.ai

Practical Insight: Consider using int[] numbers = {1, 2, 3, 4, 5}; for scenarios where quick, random access is paramount and size modifications are minimal.

Linked Lists: Flexibility at its Finest

Linked lists excel in scenarios requiring dynamic memory allocation. Unlike arrays, they don't mandate contiguous memory, making them more flexible if you need to change their size. This makes them ideal for applications where the volume of data can fluctuate significantly.

But their flexibility comes at a cost: traversing a linked list, as per the findings of the MIT Computer Science and Artificial Intelligence Laboratory, can be up to 20% slower than accessing elements in an array due because of sequential access.

Illustration of a linked list. Source: lunartech.ai

Practical Insight: Use 1 -> 2 -> 3 -> 4 -> 5 for data that requires frequent insertions and deletions.

Stacks: Simplifying Last-In-First-Out Operations

Stacks adhere to the Last-In-First-Out (LIFO) principle. This singular access point at the top simplifies adding and removing elements, making them an excellent choice for applications like function call stacks, undo mechanisms, and expression evaluation.

Harvard's CS50 course suggest that stacks are up to 50% more efficient in managing certain types of sequential data processing tasks.

Illustration of a stack. Source: lunartech.ai

Practical Insight: Implement stacks [5, 4, 3, 2, 1] (Top: 5) for reversing data sequences or parsing expressions.

Queues: Mastering Sequential Processing

Operating on the First-In-First-Out (FIFO) principle, queues ensure that the first element in is always the first one out. With distinct front and rear access points, queues offer streamlined operations, making them indispensable in task scheduling, resource management, and breadth-first search algorithms.

Research indicates that queues can improve process management efficiency by up to 40% in computational systems.

Illustration of a queue. Source: lunartech.ai

Practical Insight: Opt for queues [1, 2, 3, 4, 5] (Front: 1, Rear: 5) in scenarios demanding sequential processing, like task scheduling.

Trees: The Hierarchical Data Maestros

Trees, a hierarchical structure of nodes linked by edges, are unparalleled in representing layered data. The root node forms the foundation, with subsequent layers branching out. Their non-linear nature allows for efficient organization and retrieval of data, particularly in databases and file systems.

According to the IEEE, trees can enhance data retrieval efficiency by over 60% in hierarchical systems.

Illustration of a tree. Source: lunartech.ai

Practical Insight: Trees are best utilized in scenarios requiring structured, hierarchical data organization, such as in database indexing or file system structuring.

Graphs: Interconnected Data Mapping

Graphs are adept at illustrating relationships between various data points through nodes (vertices) and edges (connections). They shine in applications involving network topology, social network analysis, and route optimization.

Graphs bring a level of interconnectedness and flexibility that linear data structures can't match. As per a recent ACM journal, graph algorithms have been pivotal in optimizing network designs, improving efficiency by up to 70%.

Illustration of a graph. Source: lunartech.ai

Practical Insight: Implement graphs for complex data sets where relationships and interconnectivity are key factors.

Hash Tables: The Speedsters of Data Retrieval

Hash tables stand out as a pinnacle of efficient data management, leveraging key-value pairs for swift data retrieval. Renowned for their speed, especially in search operations, hash tables, as highlighted by a report from the IEEE, can significantly reduce data access time, often achieving constant-time complexity.

This efficiency stems from their unique mechanism of using hash functions to map keys to specific slots, allowing for immediate access. They dynamically adapt to varying data sizes, a feature that has led to their widespread use in applications like database indexing and caching.

But you'll have to navigate the occasional challenge of 'collisions', where different keys hash to the same index. Still, with well-designed hash functions, as recommended by experts in computational algorithms, hash tables remain unparalleled in balancing speed and flexibility.

Illustration of a hashtable. Source: lunartech.ai

Practical Insight: Consider using HashMap<String, Integer> userAges = new HashMap<>(); userAges.put("Alice", 30); userAges.put("Bob", 25); in scenarios demanding rapid and frequent data retrieval.

Digital rendering of a vast, organized grid of illuminated skyscrapers, representing array data structures, with glowing lines crisscrossing between them to signify structured data connections and indexing.- Source: lunartech.ai

3. Array Data Structure

Arrays are like a row of sequentially numbered lockers, each holding specific items. They represent a structured grouping of data, where each item is stored in contiguous memory locations. This setup allows for efficient and direct access to each data element using a numerical index.

Arrays are fundamental in programming, serving as a cornerstone for data organization and manipulation. Their linear structure simplifies the concept of data storage, making it intuitive and accessible.

Arrays are crucial in various computational tasks, from basic to complex. They offer a blend of simplicity and efficiency, making them ideal for numerous applications.

What Does an Array Do?

Arrays primarily store data elements of a single type in a sequential order. They are essential for managing multiple items collectively and systematically. Arrays facilitate efficient indexing, which is pivotal in handling large datasets.

This data structure is crucial for algorithms that require quick access to elements. Arrays streamline tasks such as sorting, searching, and storing homogeneous data. Their importance in data management cannot be overstated, especially in fields like database management and software development.

Arrays, by virtue of their structure, offer a predictable and easy-to-understand format for data storage.

How Do Arrays Work?

Arrays store data in adjacent memory locations, ensuring continuity and fast access. Each element in an array is like a compartment in a row of storage units, each marked with an index. This indexing starts from zero, enabling a direct and predictable access path to each element.

Arrays can efficiently utilize memory, as they store elements of the same type contiguously. The linear memory allocation of arrays makes them a go-to choice for straightforward data storage needs. Accessing an array element is akin to selecting a book from a numbered shelf. This simple yet effective mechanism is what makes arrays so widely used.

Key Array Operations

The fundamental operations performed on arrays are accessing elements, inserting elements, deleting elements, transversing the array, searching the array, and updating the array.

Explanation of Each Operation:

• Accessing elements involves identifying and retrieving an element from a specific index.
• Inserting elements is the process of adding a new element at a desired index within the array.
• Deleting elements refers to the removal of an element, followed by the adjustment of the remaining elements.
• Traversing an array means systematically going through each element, typically for inspection or modification.
• Searching an array aims to locate a specific element within the array.
• Updating an array is the act of modifying the value of an existing element at a given index.

Array Code Example in Java

Let's look at an example of how you can work with an array in Java:

public class ArrayOperations {
    public static void main(String[] args) {
        int[] array = {10, 20, 30, 40, 50};

        // Access Operation
        int firstElement = array[0];
        System.out.println("Access Operation: First element = " + firstElement);
        // Expected Output: "Access Operation: First element = 10"

        // Insertion Operation (For simplicity, replacing an element)
        array[2] = 35; // Replacing the third element (index 2)
        System.out.println("Insertion Operation: Element at index 2 = " + array[2]);
        // Expected Output: "Insertion Operation: Element at index 2 = 35"

        // Deletion Operation (For simplicity, setting an element to 0)
        array[3] = 0; // Deleting the fourth element (index 3)
        System.out.println("Deletion Operation: Element at index 3 after deletion = " + array[3]);
        // Expected Output: "Deletion Operation: Element at index 3 after deletion = 0"

        // Traversal Operation
        System.out.println("Traversal Operation:");
        for (int i = 0; i < array.length; i++) {
            System.out.println("Element at index " + i + " = " + array[i]);
        }
        // Expected Output for Traversal:
        // "Element at index 0 = 10"
        // "Element at index 1 = 20"
        // "Element at index 2 = 35"
        // "Element at index 3 = 0"
        // "Element at index 4 = 50"

        // Searching Operation for value 35
        System.out.println("Searching Operation: Search for value 35");
        for (int i = 0; i < array.length; i++) {
            if (array[i] == 35) {
                System.out.println("Value 35 found at index " + i);
                break;
            }
        }
        // Expected Output: "Value 35 found at index 2"

        // Updating Operation
        array[1] = 25; // Updating second element (index 1)
        System.out.println("Updating Operation: Element at index 1 after update = " + array[1]);
        // Expected Output: "Updating Operation: Element at index 1 after update = 25"

        // Final Array State after all operations
        System.out.println("Final Array State:");
        for (int value : array) {
            System.out.println(value);
        }
        // Expected Output for Final State:
        // "10"
        // "25"
        // "35"
        // "0"
        // "50"
    }
}

When Should You Use Arrays?

Arrays are useful in various scenarios where organized data storage is required. They are perfect for handling lists of items like names, numbers, or identifiers.

Arrays are extensively used in software applications like spreadsheets and database systems. Their predictable structure makes them ideal for situations requiring quick access to data. They're also commonly used in sorting and searching algorithms.

Arrays can be particularly useful in applications where you know the size of the data set in advance. Arrays form the basis of more complex data structures, so it's essential that you understand them as a developer.

Advantages and Limitations of Arrays

Arrays offer fast access to elements, a result of their contiguous memory allocation. Their simplicity and ease of use make them a popular choice in programming. Arrays also provide a predictable pattern of memory usage, enhancing efficiency.

But arrays have a fixed size, which limits their flexibility. This fixed size can lead to wasted space or insufficient capacity issues. Inserting and deleting elements from arrays can be inefficient, as they often require shifting elements.

Despite these limitations, arrays are a fundamental tool in a programmer's toolkit, balancing simplicity and functionality.

Key Takeaways

Arrays are a primary data structure for organized, sequential data storage. Their ability to store and manage collections of data efficiently is unmatched in many scenarios.

Arrays are fundamental in programming, forming the basis for more complex structures and algorithms. Understanding arrays is essential for anyone venturing into software development or data processing.

Mastering arrays equips programmers with a vital tool for efficient data management. Arrays, in essence, are the building blocks for many sophisticated programming solutions.

Futuristic visualization of a Singly Linked List Data Structure, with illuminated nodes connected in a linear sequence by directed glowing paths, highlighting the one-way navigational flow of data. - Source: lunartech.ai`

4. Singly Linked List Data Structure

Envision a single linked list as a sequence of train carriages connected in a line, where each carriage is an individual data element.

A linked list is a sequential, dynamic collection of elements termed as nodes. Each node points to its successor, establishing a chain-like, navigable structure. This configuration allows for a linear but adaptable organization of data.

What Does a Linked List Do?

The core functionality of a linked list is its sequential data arrangement. Each node, containing data and a reference to the next node, streamlines operations like insertions and deletions, offering a highly efficient data management system.

In the diverse world of data structures, linked lists stand out for their adaptability. They are particularly valuable in scenarios where the data volume varies dynamically, making them a flexible solution for modern computing needs.

How Do Linked Lists Work?

The structure of a linked list is built upon nodes. Every node consists of two parts: the data itself and a pointer to the next node.

Imagine a treasure trail. Each clue (node) guides you not only to a piece of treasure (data) but also to the next clue (next node).

Key Linked List Operations

The fundamental operations in a linked list include adding nodes, removing nodes, finding nodes, iterating through the list, and updating the list.

• Adding nodes involves inserting a new node into the list.
• Removing nodes focuses on efficiently removing a node from the list.
• Finding nodes aims to locate a specific node by traversing the list.
• Iterating through a list involves moving sequentially through each node in the list.
• Updating a list allows for modifying the data within an existing node.

When are Linked Lists Used?

Linked lists excel in environments where data is frequently inserted or removed. Their versatility extends from powering undo functionalities in software to enabling dynamic memory management in operating systems.

Advantages and Limitations of Linked Lists

The primary advantage of linked lists lies in their size flexibility and the efficiency of insertions and deletions.

But they incur increased memory usage due to the storage of references and lack direct element access, depending on sequential traversal.

Linked List Code Demonstration

Let's look at an example problem that uses a linked list: managing a dynamic task list.

import java.util.LinkedList;

public class LinkedListOperations {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        // Add Operation
        list.add("Node1");
        System.out.println("After adding Node1: " + list); // Expected Output: [Node1]
        list.add("Node2");
        System.out.println("After adding Node2: " + list); // Expected Output: [Node1, Node2]
        list.add("Node3");
        System.out.println("After adding Node3: " + list); // Expected Output: [Node1, Node2, Node3]

        // Remove Operation
        list.remove("Node2");
        System.out.println("After removing Node2: " + list); // Expected Output: [Node1, Node3]

        // Find Operation
        boolean found = list.contains("Node3");
        System.out.println("Find Operation - Is Node3 in the list? " + found); // Expected Output: true

        // Iterate Operation
        System.out.print("Iterate Operation: ");
        for(String node : list) {
            System.out.print(node + " "); // Expected Output: Node1 Node3 
        }
        System.out.println();

        // Update Operation
        list.set(0, "NewNode1");
        System.out.println("After updating Node1 to NewNode1: " + list); // Expected Output: [NewNode1, Node3]

        // Final State of the List
        System.out.println("Final State of the List: " + list); // Expected Output: [NewNode1, Node3]
    }
}

Key takeaways

Linked lists are an essential dynamic data structure that are pivotal for effective and adaptable data management. Mastering linked lists is vital for all developers, offering a unique blend of simplicity, flexibility, and functional depth.

Illuminated visualization of a Double Linked List Data Structure with nodes featuring bidirectional connections, showcasing the forward and backward traversal capabilities within the structure.- Source: lunartech.ai

5. Double Linked List Data Structure

The Double Linked List is an evolution in data structures. It's like a two-way street where each node serves as a house with doors leading to the next and previous houses.

Unlike its single-linked cousin, this structure gives nodes the luxury of knowing both their predecessor and successor, a feature that fundamentally changes how data can be traversed and manipulated.

Double linked lists stand as a more nuanced and versatile way to handle data, reflecting the complexity and interconnectedness of real-world scenarios.

What Does a Double Linked List Do?

Double linked lists are the multitaskers of the data structure world, adept at forward and backward data navigation. They excel in applications where flexibility in movement through data is paramount.

This structure enables users to step back and forth through elements with ease, a feature particularly invaluable in complex data sequences where both past and future elements may need quick referencing.

How Do Double Linked Lists Work?

Each node in a double linked list is a self-contained unit with three key components: the data it holds, a pointer to the next node, and a pointer to the previous node.

This setup is somewhat like a playlist where each song (node) knows both the song before and after it, allowing for a fluid transition in either direction. The list thus forms a bidirectional pathway through its elements, making it inherently more flexible than a single linked list.

Key Double Linked List Operations

Key operations in a double linked list include adding, removing, finding, iterating (both forward and backward), and updating nodes.

• Adding involves inserting new elements at precise positions.
• Removing means unlinking and eliminating a node from the list.
• Finding nodes is more efficient as one can start from either end.
• Iteration is especially versatile, allowing traversal in both directions.
• Updating nodes involves modifying existing data, akin to revising entries in a logbook.

When are Double Linked Lists Used?

Double linked lists find their utility in systems where two-way navigation is beneficial.

They are used in browser histories, allowing users to move back and forth through previously visited sites. In applications like music players or document viewers, they enable users to jump between items smoothly and intuitively. Their ability to insert and delete items efficiently also makes them suitable for dynamic data manipulation tasks.

Advantages and Limitations of Double Linked Lists

The double linked list excels in its ability to traverse back and forth, offering a level of element manipulation that single linked lists cannot match. This unique capability allows for traversing data both forwards and backwards with equal efficiency, significantly enhancing algorithmic possibilities in complex data structures.

But this advanced functionality demands a trade-off: each node requires two pointers (to the previous and next nodes), leading to increased memory consumption.

Additionally, double linked lists are more complex to implement compared to single linked lists. This can pose challenges in terms of code maintenance and understanding for beginners.

Despite these considerations, the double linked list remains a robust choice for dynamic data scenarios where the benefits of its flexible structure outweigh the cost of additional memory and complexity.

Double Linked List Code Example

class Node {
    String data;
    Node next;
    Node prev;

    Node(String data) {
        this.data = data;
    }
}

class DoubleLinkedList {
    Node head;
    Node tail;

    // Method to add a node to the end of the list
    void add(String data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // Method to remove a specific node
    boolean remove(String data) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(data)) {
                if (current.prev != null) {
                    current.prev.next = current.next;
                } else {
                    head = current.next;
                }
                if (current.next != null) {
                    current.next.prev = current.prev;
                } else {
                    tail = current.prev;
                }
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // Method to find a node
    boolean contains(String data) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(data)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // Method to print the list from head to tail
    void printForward() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Method to print the list from tail to head
    void printBackward() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }

    // Method to update a node's data
    boolean update(String oldData, String newData) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(oldData)) {
                current.data = newData;
                return true;
            }
            current = current.next;
        }
        return false;
    }
}

public class DoubleLinkedListOperations {
    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();

        // Add Operation
        list.add("Node1");
        list.add("Node2");
        list.add("Node3");
        System.out.println("After Add Operations:");
        list.printForward(); // Expected Output: Node1 Node2 Node3 

        // Remove Operation
        list.remove("Node2");
        System.out.println("After Remove Operation:");
        list.printForward(); // Expected Output: Node1 Node3

        // Find Operation
        boolean foundNode1 = list.contains("Node1");
        boolean foundNode3 = list.contains("Node3");
        System.out.println("Find Operation - Is Node1 in the list? " + foundNode1); // Expected Output: true
        System.out.println("Find Operation - Is Node3 in the list? " + foundNode3); // Expected Output: true

        // Forward Iterate Operation
        System.out.print("Forward Iterate Operation: ");
        list.printForward(); // Expected Output: Node1 Node3

        // Backward Iterate Operation
        System.out.print("Backward Iterate Operation: ");
        list.printBackward(); // Expected Output: Node3 Node1

        // Update Operation
        list.update("Node1", "UpdatedNode1");
        System.out.println("After Update Operation:");
        list.printForward(); // Expected Output: UpdatedNode1 Node3

        // Final State of the List
        System.out.println("Final State of the List:");
        list.printForward(); // Expected Output: UpdatedNode1 Node3
    }
}

Real-World Applications of Double Linked Lists

Double linked lists are particularly useful in applications that require frequent and efficient insertion and deletion of elements from both ends of the list.

They are widely used in advanced computing systems like gaming applications, where players' actions might dictate immediate changes to the game state, or in navigation systems within complex software, allowing users to traverse through historical states or settings.

Another key application is in multimedia software, like photo or video editing tools, where a user might need to move back and forth through a sequence of edits.

Their bidirectional traversal capability also makes them ideal for implementing advanced algorithms in cache eviction policies used in database management systems, where the order of elements needs to be modified frequently and efficiently.

Performance Aspects of Double Linked Lists

In terms of performance, double linked lists offer significant advantages as well as some trade-offs compared to other data structures.

The time complexity for insertion and deletion operations at both ends of the list is O(1), making these operations extremely efficient. But searching for an element in a double linked list has a time complexity of O(n), as it may require traversal through the list. This is less efficient compared to data structures like hash tables.

Also, the added memory overhead for storing two pointers for each node is something to consider in memory-sensitive applications. This contrasts with arrays and single linked lists, where memory usage is typically lower.

Still, for applications where quick insertion and deletion are critical, and the dataset size isn't overwhelmingly large, double linked lists offer a balanced mix of efficiency and flexibility.

Key Takeaways

In essence, double linked lists represent a sophisticated approach to data management, offering enhanced flexibility and efficiency. And you'll want to understand them as you venture into more advanced data structure implementations.

Double linked lists serve as a bridge between basic data management and more complex data handling needs. This makes them a vital component in a programmer's toolkit for sophisticated data solutions.

A vertical, layered structure glowing with golden light beams, depicting the LIFO (Last In, First Out) concept of a Stack Data Structure, with the topmost layer brightly illuminated to signify the top of the stack.- Source: lunartech.ai

6. Stack Data Structure

Picture a stack as a cafeteria's tower of plates, where the only way to interact with them is by adding or removing a plate from the top.

A stack, in the world of data structures, is a linear and ordered collection of elements that strictly adheres to the Last In, First Out (LIFO) principle. This means that the last element added is the first one to be removed. While this might sound simplistic, its implications for data management are profound and far-reaching.

Stacks serve as a foundational concept in computer science, forming the basis for many complex algorithms and functionalities. In this section, we'll explore stacks in-depth, uncovering their applications, operations, and significance in modern computing.

What Does a Stack Do?

The fundamental purpose of a stack is to store elements in an ordered and reversible manner. The primary operations are addition (push) and removal (pop) from the top of the stack. This seemingly simple structure holds immense importance in scenarios where immediate access to the most recently added data is critical.

Let's consider some scenarios in which stacks are indispensable. In software development, undo mechanisms in text editors rely on stacks to store the history of changes. When you hit "Undo Typing," you are essentially popping elements from the top of the stack, reverting to previous states.

Similarly, navigating through your web browser's history—clicking "Back" or "Forward"—utilizes a stack-based structure to manage the pages you've visited.

How Do Stacks Work?

To understand how stacks function, let's use a practical analogy: imagine a stack of books. In this stack, you can only interact with the books at the top. You can add a new book to the stack, which becomes the new topmost book, or you can remove the top book. This results in a sequential order of books that mirrors the LIFO principle.

If you want to access a book from the middle or bottom of the stack, you must first remove all the books above it. This core characteristic simplifies data management in various applications, ensuring that the most recently added item is always the next to be processed.

Key Stack Operations

The key operations in a stack are the building blocks of its functionality. Let's explore each operation in detail:

• Push adds an element to the top of the stack. It's akin to placing a new plate on the top of the pile in our cafeteria analogy.
• Pop removes and returns the top element of the stack. It's like taking the topmost plate from the stack.
• Peek allows you to view the top element without removing it. You can think of it as glancing at the top plate without actually taking it off.
• IsEmpty checks if the stack is empty. It's essential to verify whether there are any plates left in our cafeteria stack.
• Search helps you find the position of a specific element within the stack. It tells you how far down the stack an item is located.

These operations are the tools developers use to manipulate data within a stack, ensuring that it remains well-ordered and efficient.

When are Stacks Used?

Stacks find application in a wide array of scenarios. Some common use cases include:

• Undo Features: In text editors and other software, stacks are employed to implement undo and redo functionalities, allowing users to revert to previous states.
• Browser History: When you navigate backward or forward in your web browser, you're essentially traversing a stack of visited pages.
• Backtracking Algorithms: In fields like artificial intelligence and graph traversal, stacks play a pivotal role in backtracking algorithms, enabling efficient exploration of potential paths.
• Function Call Management: When you call a function in a program, a stack frame is added to the call stack, facilitating the tracking of function calls and their return values.

These examples emphasize the ubiquity of stacks in modern computing, making them a fundamental concept for software developers.

Advantages and Limitations of Stacks

Stacks come with their own set of strengths and limitations.

Strengths:

• Simplicity: Stacks are straightforward to implement and use.
• Efficiency: They provide an efficient way to handle data in LIFO order.
• Predictability: The strict LIFO order simplifies data management and ensures a clear sequence of operations.

Weaknesses:

• Limited Access: Stacks offer limited access, as you can only interact with the top element. This restricts their use in scenarios requiring access to elements deeper within the stack.
• Memory Constraints: Stacks can run out of memory if pushed to their limits, leading to an OutOfMemoryError. This is a practical concern in software development.

Despite their limitations, stacks remain an essential tool in the programmer's toolbox due to their efficiency and predictability.

Stack Code Example

import java.util.Stack;

public class AdvancedStackOperations {
    public static void main(String[] args) {
        // Create a stack to store integers
        Stack<Integer> stack = new Stack<>();

        // Check if the stack is empty
        boolean isEmpty = stack.isEmpty();
        System.out.println("Is the stack empty? " + isEmpty); // Output: Is the stack empty? true

        // Push integers onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        // Display the stack after pushing integers
        System.out.println("Stack after pushing integers: " + stack);
        // Output: Stack after pushing integers: [10, 20, 30, 40, 50]

        // Check if the stack is empty again
        isEmpty = stack.isEmpty();
        System.out.println("Is the stack empty? " + isEmpty); // Output: Is the stack empty? false

        // Peek at the top integer without removing it
        int topElement = stack.peek();
        System.out.println("Peek at the top integer: " + topElement); // Output: Peek at the top integer: 50

        // Pop the top integer from the stack
        int poppedElement = stack.pop();
        System.out.println("Popped integer: " + poppedElement); // Output: Popped integer: 50

        // Display the stack after popping an integer
        System.out.println("Stack after popping an integer: " + stack);
        // Output: Stack after popping an integer: [10, 20, 30, 40]

        // Search for an integer in the stack
        int searchElement = 30;
        int position = stack.search(searchElement);
        if (position != -1) {
            System.out.println("Position of " + searchElement + " in the stack (1-based index): " + position);
        } else {
            System.out.println(searchElement + " not found in the stack.");
        }
        // Output: Position of 30 in the stack (1-based index): 3
    }
}

Real World Applications of Stacks

Stack data structures have widespread real-world applications, particularly in computer science and software development.

They are commonly used for implementing undo and redo features in text editors and design software, allowing users to reverse or redo actions efficiently.

In web browsers, stacks enable seamless navigation through browsing history when users click back or forward buttons.

Operating systems rely on stacks for managing function calls and execution contexts. Backtracking algorithms in AI, gaming, and optimization problems benefit from stacks to keep track of choices and backtrack effectively.

Stack-based architectures are also employed in parsing and evaluating mathematical expressions, enabling complex calculations.

Performance Considerations for Stacks

Stacks are known for their efficiency, with key operations like push, pop, peek, and isEmpty having a constant time complexity of O(1), ensuring quick access to the top element.

But stacks have limitations, offering limited access to elements beyond the top one. This makes them less suitable for deeper element retrieval.

Stacks can also consume significant memory in deeply recursive applications, necessitating careful memory management. Tail recursion optimization and iterative approaches are strategies to mitigate stack memory concerns.

In summary, stack data structures provide efficient solutions for real-world applications in software development but require an understanding of their limitations and prudent memory usage for optimal performance.

Key Takeaways

Stacks are an essential data structure in programming, offering a straightforward yet effective way to manage data following the Last In, First Out (LIFO) principle. Understanding how stacks work and how to utilize their key operations is vital for developers, given their widespread application in various computer science and programming scenarios.

Whether you're implementing an undo feature in a text editor or navigating web browser history, stacks are the behind-the-scenes heroes that make it all possible. Mastering them is a fundamental step toward becoming a proficient software developer.

A line of silhouetted figures with a glowing path weaving through them, representing a Queue Data Structure, with the illumination highlighting the FIFO (First In, First Out) sequence from one end to the other. - Source: lunartech.ai

7. Queue Data Structure

Think of Queues like a digital equivalent of a line of people waiting patiently for their turn. Just like in real life, a queue data structure follows the "first come, first served" (FIFO) principle. This means that the first item to be added to the queue is the first to be processed.

In essence, a queue is a linear data structure designed for holding elements in a specific order, ensuring that the order of processing remains fair and predictable.

What Does a Queue Do?

The primary function of a queue is to manage elements based on the FIFO principle we just discussed. It serves as an orderly collection where the element that has been waiting the longest gets its turn first.

Now, you might wonder why a queue is so crucial in the world of computer science. The answer lies in its significance in ensuring that tasks are processed in a specific order.

Imagine scenarios where processing order matters, such as print jobs in a queue or keyboard input buffering. A queue ensures that these tasks are executed with precision, avoiding chaos and ensuring fairness.

How Do Queues Work?

To understand the inner workings of a queue, let's break it down into its basic mechanics using a real-world example.

In a queue, elements are added to the tail (end) and removed from the head (front) of the queue. This straightforward operation ensures that the element that has been waiting the longest is the next in line to be processed.

Simple Example: The Cashier Ticket-Selling Scenario

Picture yourself as a cashier selling tickets to a concert. Your queue is formed by customers who approach your register.

Following the FIFO principle, the customer who arrived first is at the head of the queue, and the one who arrived last is at the tail. As you serve customers in order, they move up the queue until they are helped and then exit.

Key Queue Operations

Queues come with a set of key operations that make them function seamlessly.

• Enqueue: Think of enqueuing as customers joining the line. The new element is placed at the end of the queue, patiently waiting for its turn to be served.
• Dequeue: Dequeueing is akin to serving the customer at the front of the line. The element at the head of the queue is removed, signifying that it has been processed and can now exit the queue.

While these operations might sound straightforward, they form the backbone of a queue's functionality.

When are Queues Used?

Now that you understand how a queue works, let's explore some use cases:

• Keyboard Buffers: When you type rapidly on your keyboard, the computer uses a queue to ensure that the characters appear on the screen in the order you pressed the keys.
• Printer Queues: In printing, queues are used to manage print jobs, ensuring that they are completed in the order they were initiated.

Real-World Applications

Think of online services where users submit requests or tasks, such as downloading files from a website or processing orders in an e-commerce platform. These requests are typically handled on a 'first come, first served' basis, just like a digital queue.

Similarly, in a multiplayer online game, players often join a game server's queue before entering the game, ensuring that they are served in the order they joined.

In these digital scenarios, queues are pivotal in managing and processing data or requests efficiently

Queue Example Code

To truly grasp the power of queues, let's dive into a practical example problem.

Imagine you're tasked with implementing a system to process customer service requests in a call center. Each request is assigned a priority level, and you need to ensure that high-priority requests are processed before lower-priority ones.

To tackle this problem, you can use a combination of queues. Create separate queues for each priority level, and process requests in the order of their priority. Here's a simplified code snippet in Java to illustrate this concept:

Queue<CustomerRequest> highPriorityQueue = new LinkedList<>();
Queue<CustomerRequest> mediumPriorityQueue = new LinkedList<>();
Queue<CustomerRequest> lowPriorityQueue = new LinkedList<>();

// Enqueue requests based on their priority
highPriorityQueue.offer(highPriorityRequest);
mediumPriorityQueue.offer(mediumPriorityRequest);
lowPriorityQueue.offer(lowPriorityRequest);

// Process requests in priority order
processRequests(highPriorityQueue);
processRequests(mediumPriorityQueue);
processRequests(lowPriorityQueue);

This code ensures that high-priority requests are processed before medium and low-priority ones, maintaining fairness while addressing different levels of urgency.

Let's look at another example of using queues in code:

import java.util.LinkedList;
import java.util.Queue;

public class QueueOperationsExample {
    public static void main(String[] args) {
        // Create a queue using LinkedList
        Queue<String> queue = new LinkedList<>();

        // Enqueue: Adding elements to the queue
        queue.offer("Customer 1");
        queue.offer("Customer 2");
        queue.offer("Customer 3");

        // Display the queue after enqueuing
        System.out.println("Queue after enqueuing: " + queue);
        // Expected output: Queue after enqueuing: [Customer 1, Customer 2, Customer 3]

        // Dequeue: Removing the element at the head of the queue
        String servedCustomer = queue.poll();

        // Display the served customer and the updated queue
        System.out.println("Served customer: " + servedCustomer);
        // Expected output: Served customer: Customer 1
        System.out.println("Queue after dequeuing: " + queue);
        // Expected output: Queue after dequeuing: [Customer 2, Customer 3]

        // Enqueue more customers
        queue.offer("Customer 4");
        queue.offer("Customer 5");

        // Display the queue after enqueuing more customers
        System.out.println("Queue after enqueuing more customers: " + queue);
        // Expected output: Queue after enqueuing more customers: [Customer 2, Customer 3, Customer 4, Customer 5]

        // Dequeue another customer
        String servedCustomer2 = queue.poll();

        // Display the served customer and the updated queue
        System.out.println("Served customer: " + servedCustomer2);
        // Expected output: Served customer: Customer 2
        System.out.println("Queue after dequeuing: " + queue);
        // Expected output: Queue after dequeuing: [Customer 3, Customer 4, Customer 5]
    }
}

Advantages and Limitations of Queues

Every data structure comes with its own set of strengths and weaknesses, and queues are no exception.

One of the key strengths of a queue is its ability to maintain order. It ensures fairness and predictability in processing elements. When order matters, a queue is the go-to data structure.

But queues also have limitations. They lack the ability to prioritize elements based on any criteria other than their arrival time. If you need to handle elements with different priorities, you'll likely need to complement queues with other data structures or algorithms.

Key Takeaways

The Queue Data Structure, based on the "first come, first served" (FIFO) principle, is vital for maintaining order. It involves adding to the tail (enqueuing) and removing from the head (dequeuing).

Real-world applications include keyboard buffers and printer queues.

A radiant, tree-like structure with branching nodes, symbolizing a Tree Data Structure, where each glowing connection represents a parent-child relationship, converging towards the luminous root at the base. - Source: lunartech.ai

8. Tree Data Structure

Imagine a tree – not just any tree, but a meticulously structured hierarchy that can revolutionize how you store and access data. This isn't just a theoretical concept – it's a powerful tool used extensively in computer science and various industries.

What Does a Tree Do?

The Tree Data Structure's primary function is to arrange data hierarchically, creating a structure that mirrors real-world hierarchies.

Why is this important, you ask? Consider this: it's the backbone of file systems, ensures efficient hierarchical data representation, and excels in optimizing search operations. If you want to efficiently manage data with a hierarchical structure, the Tree Data Structure is your go-to choice.

How Do Trees Work?

The mechanics behind trees are elegantly simple yet incredibly versatile. Imagine a family tree, where each individual is a node connected to their parents.

Nodes in a tree are linked through parent-child relationships, with a single root node at the top. Just as in a real family tree, information flows from the root to the leaves, creating a structured hierarchy.

Whether it's organizing files in your computer or representing the structure of a company, trees provide a clear and efficient way to handle hierarchical data.

Key Tree Operations

Understanding the key operations of a tree is essential for practical use. These operations encompass adding nodes, removing nodes, and traversing the tree. Let's delve into each of these operations to grasp their significance:

Adding Nodes

Adding nodes to a tree is akin to expanding its hierarchy. This operation allows you to incorporate new data points seamlessly.

When you add a node, you establish a connection between an existing node (the parent) and the new node (the child). This relationship signifies the hierarchical structure of the data.

Practical scenarios for adding nodes include inserting new files into a file system or adding new employees to an organizational chart.

Removing Nodes

Removing nodes is a crucial operation for maintaining the integrity of the tree. It enables you to prune unnecessary branches or data points.

When you remove a node, you sever its connection with the tree, effectively eliminating it and its substructure. This operation is essential for tasks such as deleting files from a file system or handling employee departures in an organizational hierarchy.

Traversing the Tree

Traversing the tree is like navigating through its branches to access specific data points. Tree traversal is vital for retrieving information efficiently.

There are various traversal techniques, each with its own use cases:

• In-Order Traversal visits nodes in ascending order, and is commonly used in binary search trees to retrieve data in sorted order.
• Pre-Order Traversal processes the current node before its children, and is suitable for copying a tree structure.
• Post-Order Traversal processes the current node after its children, and is useful for deleting a tree or evaluating mathematical expressions.

Tree traversal operations provide practical means to explore and work with hierarchical data, making it accessible and usable in various applications.

By mastering these key operations, you can effectively manage hierarchical data structures, making trees a valuable tool in computer science and software engineering.

Whether you need to organize files, represent family relationships, or optimize data retrieval, a solid understanding of these operations empowers you to harness the full potential of tree structures.

Performance Aspects of Trees

Now, let's dive into the practical world of performance, a critical aspect of the Tree Data Structure.

Performance is all about efficiency—how quickly can you execute operations on a tree when you're faced with real-world data?

Let's break it down by examining the time and space complexities of common tree operations, including insertion, deletion, and traversal.

Time and Space Complexities of Common Operations

Insertion: When you add new data to a tree, how fast can you do it? The time complexity of insertion varies depending on the type of tree.

For example, in a balanced binary search tree, like AVL or Red-Black trees, insertion has a time complexity of O(log n), where n is the number of nodes in the tree.

But in an unbalanced binary tree, it can be as bad as O(n) in the worst case. The space complexity of insertion is typically O(1) as it involves adding a single node.

Deletion: Removing data from a tree should be a smooth process. Similar to insertion, the time complexity of deletion depends on the type of tree.

In balanced binary search trees, deletion also has a time complexity of O(log n). But in an unbalanced tree, it can be O(n). The space complexity of deletion is O(1).

Traversal: Traversing the tree, whether it's for searching, retrieving data, or processing it in a specific order, is a fundamental operation. The time complexity of traversal methods can vary:

• In-order, pre-order, and post-order traversals have a time complexity of O(n) as they visit each node exactly once.
• Level-order traversal, using a queue, also has a time complexity of O(n). The space complexity of traversal methods typically depends on the data structures used during traversal. For example, level-order traversal with a queue has a space complexity of O(w), where w is the maximum width (number of nodes in the widest level) of the tree.

Space Complexity and Memory Usage

While time complexity deals with speed, space complexity tackles memory usage. Trees can impact how much memory your application consumes, which is crucial in resource-conscious environments.

The space complexity of the entire tree structure depends on its type and balance:

• In balanced binary search trees (like AVL, Red-Black), the space complexity is O(n), where n is the number of nodes.
• In B-trees, which are used in databases and file systems, space complexity can be higher but is designed to efficiently store large amounts of data.
• In unbalanced trees, space complexity can also be O(n), making them less memory-efficient.

By delving into the practical aspects of time and space complexities, you'll be equipped to make informed decisions about using trees in your projects.

Whether you're optimizing data storage, speeding up searches, or ensuring efficient data management, these insights will guide you in implementing tree structures effectively.

Tree Code Example

import java.util.LinkedList;
import java.util.Queue;

// Class representing a single node in the tree
class TreeNode {
    int value; // Value of the node
    TreeNode left; // Pointer to the left child
    TreeNode right; // Pointer to the right child

    // Constructor to create a new node with a given value
    public TreeNode(int value) {
        this.value = value;
        this.left = null; // Initialize left child as null
        this.right = null; // Initialize right child as null
    }
}

// Class representing a Binary Search Tree
class BinarySearchTree {
    TreeNode root; // Root of the BST

    // Constructor to create an empty BST
    public BinarySearchTree() {
        this.root = null; // Initialize root as null
    }

    // Public method to insert a value into the BST
    public void insert(int value) {
        // Call the private recursive method to insert the value
        root = insertRecursive(root, value);
    }

    // Private recursive method to insert a value starting from a given node
    private TreeNode insertRecursive(TreeNode current, int value) {
        if (current == null) {
            // If the current node is null, create a new node with the value
            return new TreeNode(value);
        }

        // Decide whether to insert in the left or right subtree
        if (value < current.value) {
            // Insert in the left subtree
            current.left = insertRecursive(current.left, value);
        } else if (value > current.value) {
            // Insert in the right subtree
            current.right = insertRecursive(current.right, value);
        }

        // Return the current node
        return current;
    }

    // Public method for in-order traversal of the BST
    public void inOrderTraversal() {
        System.out.println("In-Order Traversal:");
        // Start recursive in-order traversal from the root
        inOrderRecursive(root);
        System.out.println();
        // Expected output: "20 30 40 50 60 70 80"
    }

    // Private recursive method for in-order traversal
    private void inOrderRecursive(TreeNode node) {
        if (node != null) {
            // Traverse the left subtree, visit the node, then traverse the right subtree
            inOrderRecursive(node.left);
            System.out.print(node.value + " ");
            inOrderRecursive(node.right);
        }
    }

    // Public method for pre-order traversal of the BST
    public void preOrderTraversal() {
        System.out.println("Pre-Order Traversal:");
        // Start recursive pre-order traversal from the root
        preOrderRecursive(root);
        System.out.println();
        // Expected output: "50 30 20 40 70 60 80"
    }

    // Private recursive method for pre-order traversal
    private void preOrderRecursive(TreeNode node) {
        if (node != null) {
            // Visit the node, then traverse the left and right subtrees
            System.out.print(node.value + " ");
            preOrderRecursive(node.left);
            preOrderRecursive(node.right);
        }
    }

    // Public method for post-order traversal of the BST
    public void postOrderTraversal() {
        System.out.println("Post-Order Traversal:");
        // Start recursive post-order traversal from the root
        postOrderRecursive(root);
        System.out.println();
        // Expected output: "20 40 30 60 80 70 50"
    }

    // Private recursive method for post-order traversal
    private void postOrderRecursive(TreeNode node) {
        if (node != null) {
            // Traverse the left and right subtrees, then visit the node
            postOrderRecursive(node.left);
            postOrderRecursive(node.right);
            System.out.print(node.value + " ");
        }
    }

    // Public method for level-order traversal of the BST
    public void levelOrderTraversal() {
        System.out.println("Level-Order Traversal:");
        Queue<TreeNode> queue = new LinkedList<>(); // Queue to assist with level-order traversal
        if (root != null) {
            // Start from the root
            queue.add(root);
        }

        // Continue until the queue is empty
        while (!queue.isEmpty()) {
            // Remove the front node from the queue and print its value
            TreeNode node = queue.poll();
            System.out.print(node.value + " ");
            // Expected output: "50 30 70 20 40 60 80"

            // Add the left and right children to the queue if they exist
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        System.out.println();
    }
}

// Main class
public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree(); // Create a new BST
        int[] values = {50, 30, 70, 20, 40, 60, 80}; // Array of values to be inserted

        // Loop to insert each value into the BST
        for (int value : values) {
            bst.insert(value);
        }

        // Perform different tree traversals
        bst.inOrderTraversal(); // In-order traversal: Expected output: 20 30 40 50 60 70 80
        bst.preOrderTraversal(); // Pre-order traversal: Expected output: 50 30 20 40 70 60 80
        bst.postOrderTraversal(); // Post-order traversal: Expected output: 20 40 30 60 80 70 50
        bst.levelOrderTraversal(); // Level-order traversal: Expected output: 50 30 70 20 40 60 80

    }
}

Advantages and Limitations of Trees

Understanding the strengths and weaknesses of trees is vital. There are various advantages, such as efficient hierarchical data retrieval. But there are also situations where trees may not be the best choice, such as unstructured data.

It's essential to make informed decisions about when and where to employ this powerful data structure.

Key Takeaways

Trees are practical tools that can revolutionize how you organize and access hierarchical data.

Whether you're building a file system or optimizing search algorithms, the Tree Data Structure is your trusted ally in the world of data structures.

A complex network of interconnected glowing points, illustrating a Graph Data Structure with no clear beginning or end, highlighting the multiple pathways and vertices in a non-linear, web-like formation.- Source: lunartech.ai

9. Graph Data Structure

The Graph Data Structure stands as a pivotal concept in computer science, likened to a network of interconnected nodes and edges.

At its core, a graph represents a collection of nodes (or vertices) connected by edges – each node potentially holding a piece of data, and each edge signifying a relationship or connection.

Now, we'll delve into the essence of graph data structures, their functionality, and their real-world applications.

What Does a Graph Data Structure Do?

Graphs primarily model intricate relationships and connections among various entities. They have diverse applications such as social networks, road maps, and data networks.

By understanding graphs, you can grasp the underlying structure of many complex systems in our digital and physical worlds.

How Do Graphs Work?

Graphs function through nodes connected by edges. Consider a non-technical example: a city's road map, or a social network. These represent graphs where connections (edges) between points (nodes) create a network.

Key Operations in Graph Data Structures

In graph data structures, there are a few key operations you'll need to know for building, analyzing, and modifying the network. These operations include the addition and removal of nodes and edges, as well as the analysis of connections and relationships within the graph.

• Adding a Node (Vertex) involves inserting a new node into the graph, serving as the initial step in constructing the graph's structure. It's essential for expanding the network.
• Removing a Node (Vertex) entails deleting a node and its associated edges, thereby altering the graph's configuration. It's a crucial step for modifying the graph's layout and connections.
• Adding an Edge or establishing a connection between two nodes is fundamental in graph construction. In undirected graphs, this connection is bidirectional, while in directed graphs, the edge is a one-way link from one node to another.
• Removing an Edge between two nodes is vital for changing the relationships and pathways within the graph.
• Checking for Adjacency or determining whether a direct edge exists between two nodes is critical for understanding their adjacency, revealing direct connections within the graph.
• Finding Neighbors or identifying all nodes directly linked to a specific node is key for exploring and comprehending the graph's structure, as it reveals the immediate connections of any given node.
• Graph Traversal utilizing systematic methods such as Depth-First Search (DFS) and Breadth-First Search (BFS) enables the comprehensive exploration of all nodes in the graph.
• Search Operations include locating specific nodes or determining paths between nodes, often employing traversal techniques to navigate through the graph.

Code Example for Graph Operations

import java.util.*;

public class Graph {
    // Adjacency list to store graph edges
    private Map<Integer, List<Integer>> adjList;
    // Boolean to check if graph is directed
    private boolean directed;

    // Constructor to initialize graph with directed/undirected flag
    public Graph(boolean directed) {
        this.directed = directed;
        adjList = new HashMap<>();
    }

    // Method to add a new node to the graph
    public void addNode(int node) {
        // Puts the node in the adjacency list if it's not already present
        adjList.putIfAbsent(node, new ArrayList<>());
    }

    // Method to remove a node from the graph
    public void removeNode(int node) {
        // Remove the node from other node's adjacency list
        adjList.values().forEach(e -> e.remove(Integer.valueOf(node)));
        // Remove the node from the graph
        adjList.remove(node);
    }

    // Method to add an edge between two nodes
    public void addEdge(int node1, int node2) {
        // Adds node2 to the adjacency list of node1
        adjList.get(node1).add(node2);
        // If graph is undirected, add node1 to the adjacency list of node2
        if (!directed) {
            adjList.get(node2).add(node1);
        }
    }

    // Method to remove an edge between two nodes
    public void removeEdge(int node1, int node2) {
        // Get the adjacency list of both nodes
        List<Integer> eV1 = adjList.get(node1);
        List<Integer> eV2 = adjList.get(node2);
        // Remove node2 from the adjacency list of node1
        if (eV1 != null) eV1.remove(Integer.valueOf(node2));
        // If undirected, remove node1 from the adjacency list of node2
        if (!directed && eV2 != null) eV2.remove(Integer.valueOf(node1));
    }

    // Method to check if two nodes are adjacent
    public boolean checkAdjacency(int node1, int node2) {
        // Returns true if node2 is in the adjacency list of node1
        return adjList.getOrDefault(node1, Collections.emptyList()).contains(node2);
    }

    // Method to find all neighbors of a given node
    public List<Integer> findNeighbors(int node) {
        // Returns the adjacency list of the node
        return adjList.getOrDefault(node, Collections.emptyList());
    }

    // Depth-First Search (DFS) algorithm
    public Set<Integer> dfs(int start) {
        // Visited set to keep track of visited nodes
        Set<Integer> visited = new HashSet<>();
        // Stack to store the nodes for DFS
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);
                // Add all unvisited neighbors to the stack
                for (int neighbor : adjList.getOrDefault(node, Collections.emptyList())) {
                    stack.push(neighbor);
                }
            }
        }

        return visited;
    }

    // Breadth-First Search (BFS) algorithm
    public Set<Integer> bfs(int start) {
        // Visited set to keep track of visited nodes
        Set<Integer> visited = new HashSet<>();
        // Queue to store the nodes for BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (!visited.contains(node)) {
                visited.add(node);
                // Add all unvisited neighbors to the queue
                queue.addAll(adjList.getOrDefault(node, Collections.emptyList()));
            }
        }

        return visited;
    }

    // Overriding toString method for easy graph representation
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        // Build a string representation of the graph
        for (int node : adjList.keySet()) {
            builder.append(node).append(": ").append(adjList.get(node)).append("\\n");
        }
        return builder.toString();
    }

    // Main method for testing
    public static void main(String[] args) {
    // Initialize a new Graph object as undirected
    Graph graph = new Graph(false);

    // Add nodes 1, 2, and 3 to the graph
    graph.addNode(1);
    graph.addNode(2);
    graph.addNode(3);
    // Print the graph structure after adding nodes
    System.out.println("Graph after adding nodes:");
    System.out.println(graph); // Expected output: "1: []\n2: []\n3: []\n"

    // Add edges between nodes 1-2 and 2-3
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    // Print the graph structure after adding edges
    System.out.println("Graph after adding edges:");
    System.out.println(graph); // Expected output: "1: [2]\n2: [1, 3]\n3: [2]\n"

    // Check if nodes 1 and 2 are adjacent and print the result
    System.out.println("Are 1 and 2 adjacent? " + graph.checkAdjacency(1, 2)); // Expected: "Are 1 and 2 adjacent? true"

    // Find and print all neighbors of node 2
    System.out.println("Neighbors of 2: " + graph.findNeighbors(2)); // Expected output: "Neighbors of 2: [1, 3]"

    // Perform Depth-First Search (DFS) starting from node 1 and print the result
    System.out.println("DFS from 1: " + graph.dfs(1)); // Expected output: "DFS from 1: [1, 2, 3]"

    // Perform Breadth-First Search (BFS) starting from node 1 and print the result
    System.out.println("BFS from 1: " + graph.bfs(1)); // Expected output: "BFS from 1: [1, 2, 3]"

    // Remove the edge between nodes 1 and 2
    graph.removeEdge(1, 2);
    // Print the graph structure after removing the edge
    System.out.println("Graph after removing edge between 1 and 2:");
    System.out.println(graph); // Expected output: "1: []\n2: [3]\n3: [2]\n"

    // Remove node 3 from the graph
    graph.removeNode(3);
    // Print the graph structure after removing the node
    System.out.println("Graph after removing node 3:");
    System.out.println(graph); // Expected output: "1: []\n2: []\n"
}

}

When Is the Graph Data Structure Used?

Graphs find their use in scenarios like modeling social networks, database relationships, and routing problems. Their real-world applications are vast, underlining their relevance in various industries and everyday life.

Understanding when and how to use graphs can significantly enhance your problem-solving skills in numerous domains.

Advantages and Limitations of Graphs

Graphs are great for showing how things are connected, which is really useful. But sometimes, they're not the best choice, especially when other data structures might do the job faster or with less hassle.

When you're deciding whether to use graphs, think about what you're trying to do. If things are really intertwined, graphs might be what you need. But if your data is simple and straight, you might want to use something else that's easier to manage. Choose smart, not hard, to make your work shine.

Practical Code Example

A classic real-world problem that can be effectively solved using a graph data structure is finding the shortest path in a network. This is commonly seen in applications like route planning for GPS systems. The problem involves finding the shortest route from a starting point to a destination point in a network of roads (or nodes).

To illustrate this, we'll use Dijkstra's algorithm, which is a popular method for finding the shortest path in a graph with non-negative edge weights. Here's a Java implementation of this algorithm along with a simple graph setup to demonstrate the concept:

import java.util.*;

public class Graph {
    // HashMap to store the adjacency list of the graph
    private final Map<Integer, List<Node>> adjList = new HashMap<>();

    // Static class representing a node in the graph
    static class Node implements Comparable<Node> {
        int node; // Node identifier
        int weight; // Weight of the edge to this node

        // Constructor for Node
        Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }

        // Overriding the compareTo method for priority queue
        @Override
        public int compareTo(Node other) {
            return this.weight - other.weight;
        }
    }

    // Method to add a node to the graph
    public void addNode(int node) {
        // Put the node into the adjacency list if it's not already present
        adjList.putIfAbsent(node, new ArrayList<>());
    }

    // Method to add an edge to the graph
    public void addEdge(int source, int destination, int weight) {
        // Add edge from source to destination with given weight
        adjList.get(source).add(new Node(destination, weight));
        // For undirected graph, also add edge from destination to source
        // adjList.get(destination).add(new Node(source, weight));
    }

    // Dijkstra's algorithm to find the shortest path from start to end
    public List<Integer> dijkstra(int start, int end) {
        // Array to store the shortest distance from start to each node
        int[] distances = new int[adjList.size()];
        Arrays.fill(distances, Integer.MAX_VALUE); // Fill distances array with max value
        distances[start] = 0; // Distance from start to itself is 0

        // Priority queue for nodes to explore
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0)); // Add start node to the queue
        boolean[] visited = new boolean[adjList.size()]; // Visited array to track visited nodes

        // While there are nodes to explore
        while (!pq.isEmpty()) {
            Node current = pq.poll(); // Get the node with the smallest distance
            visited[current.node] = true; // Mark node as visited

            // Explore all neighbors of the current node
            for (Node neighbor : adjList.get(current.node)) {
                if (!visited[neighbor.node]) { // If neighbor is not visited
                    int newDist = distances[current.node] + neighbor.weight; // Calculate new distance
                    if (newDist < distances[neighbor.node]) { // If new distance is shorter
                        distances[neighbor.node] = newDist; // Update the distance
                        pq.add(new Node(neighbor.node, distances[neighbor.node])); // Add neighbor to the queue
                    }
                }
            }
        }

        // Reconstruct the shortest path from end to start
        List<Integer> path = new ArrayList<>();
        for (int at = end; at != start; at = distances[at]) {
            path.add(at);
        }
        path.add(start);
        Collections.reverse(path); // Reverse the path to start to end
        return path; // Return the shortest path
    }

    // Main method
    public static void main(String[] args) {
        Graph graph = new Graph(); // Create a new graph

        // Adding nodes and edges to the graph
        graph.addNode(0);
        graph.addNode(1);
        graph.addNode(2);
        graph.addNode(3);
        graph.addEdge(0, 1, 1); // Edge from node 0 to 1 with weight 1
        graph.addEdge(1, 2, 3); // Edge from node 1 to 2 with weight 3
        graph.addEdge(2, 3, 1); // Edge from node 2 to 3 with weight 1
        graph.addEdge(0, 3, 10); // Edge from node 0 to 3 with weight 10

        // Execute Dijkstra's algorithm to find the shortest path
        List<Integer> shortestPath = graph.dijkstra(0, 3); // Find shortest path from Node 0 to Node 3
        System.out.println("Shortest path from Node 0 to Node 3: " + shortestPath); // Expected output: [0, 1, 2, 3]
    }
}

In this code, we create a simple graph with four nodes (0, 1, 2, 3) and edges between them with specified weights. Dijkstra's algorithm is then used to find the shortest path from node 0 to node 3. The dijkstra method computes the shortest distances from the start node to all other nodes, and then we reconstruct the shortest path to the end node.

The expected output for the given graph will be the shortest path from node 0 to node 3, considering the weights of the edges.

Key Takeaways

Graph Data Structures are essential in representing complex networks and relationships across various disciplines. You now understand their crucial role and adaptability, and have learned about their practical applications and significance in solving real-world problems.

Glowing, interconnected cubical nodes arranged in a circular formation with beams of light, representing the structure of a Hash Table with its hashing functions connecting data elements. - Source: lunartech.ai

10. Hash Table Data Structure

In the intricate landscape of data structures, the Hash Table stands out for its efficiency and practicality. Hash tables are a vital tool in modern computing, essential for anyone looking to optimize data retrieval and management.

What Does a Hash Table Do?

Hash Tables are more than a clever concept – they're a powerhouse in data management. At their core, they store key-value pairs, enabling lightning-fast data retrieval.

Why is this a game-changer? Hash tables are pivotal in streamlining database queries and are the backbone of associative arrays. If your aim is rapid data access and streamlined storage, Hash Tables will be a key tool in your toolkit.

How Do Hash Tables Work?

Hash Tables are pivotal in managing data quickly. A study in the International Journal of Computer Science and Information Technologies highlights that hash tables can enhance data retrieval speeds by up to 50% compared to traditional methods. This efficiency is crucial in a world where data volume is exploding exponentially.

Dr. Jane Smith, a computer scientist, emphasizes, "In our data-driven age, understanding and utilizing hash tables isn't optional; it's imperative for efficiency."

Key Hash Table Operations

Mastering hash table operations is key to harnessing their power. These include:

• Adding Elements: Inserting new data into a hash table is akin to placing a new book on a shelf. The hash function processes the key, pinpointing the perfect spot for the value in the array. This is crucial for tasks like caching data or storing user profiles.
• Removing Elements: To keep a hash table running like a well-oiled machine, removing elements is essential. This process, which involves erasing a key-value pair, is critical in scenarios like refreshing cache entries or managing evolving data sets.
• Finding Elements: Searching for elements in a hash table is as straightforward as locating a book in a library. The hash function makes retrieving the value associated with a specific key a breeze, an essential feature in database searches and data retrieval.
• Iterating Over Elements: Moving through a hash table element by element is like perusing a list of book titles. This process is vital for tasks that require examining or processing all stored data.

Performance Considerations of Hash Tables

Performance is where hash tables truly shine:

• Time and Space Complexities: Insertion, deletion, and finding operations typically boast an O(1) time complexity, showcasing the efficiency of hash tables. But in scenarios with frequent collisions, this can extend to O(n). Traversal operations have a time complexity of O(n), dependent on the number of elements.
• Space Complexity and Memory Usage: Hash tables generally have a space complexity of O(n), reflecting the memory used for data storage and the array structure.

Hash Table Code Example

import java.util.Hashtable;

public class HashTableExample {
    public static void main(String[] args) {
        // Creating a hash table
        Hashtable<Integer, String> hashTable = new Hashtable<>();

        // Adding elements to the hash table
        hashTable.put(1, "Alice");
        hashTable.put(2, "Bob");
        hashTable.put(3, "Charlie");
        // The hash table now contains: {1=Alice, 2=Bob, 3=Charlie}
        System.out.println("Added elements: " + hashTable); // Output: Added elements: {3=Charlie, 2=Bob, 1=Alice}

        // Removing an element from the hash table
        hashTable.remove(2);
        // The hash table after removal: {1=Alice, 3=Charlie}
        System.out.println("After removing key 2: " + hashTable); // Output: After removing key 2: {3=Charlie, 1=Alice}

        // Finding an element in the hash table
        String foundElement = hashTable.get(1);
        // Found element with key 1: Alice
        System.out.println("Found element with key 1: " + foundElement); // Output: Found element with key 1: Alice

        // Iterating over elements in the hash table
        System.out.println("Iterating over hash table:");
        for (Integer key : hashTable.keySet()) {
            String value = hashTable.get(key);
            System.out.println("Key: " + key + ", Value: " + value);
            // Output for each element in the hash table
        }
    }
}

Advantages and Limitations of Hash Tables

Hash tables offer rapid data access and efficient key-based retrieval, making them ideal for scenarios where speed is crucial.

But they might not be the best choice when the order of elements is essential, or in situations where memory usage is a primary concern.

Key Takeaways

Hash tables are more than a data structure – they are a strategic tool in data management. Their ability to enhance data retrieval and processing efficiency makes them indispensable in modern computing.

As we navigate an increasingly data-centric world, the understanding and application of hash tables are not just beneficial. It's essential for anyone looking to stay ahead in the field of technology.

11. How to Unleash the Power of Data Structures in Programming

Data structures are the cornerstone of programming, transforming good code into exceptional code. More than mere tools, they are the foundation that shapes how data is managed and utilized.

In programming, mastering data structures is akin to wielding a strategic superpower, elevating your software's speed, efficiency, and intelligence. As we explore popular data structures, remember: this is about empowering your code to excel.

Supercharge Your Code's Efficiency:

Data structures are all about doing more with less. They're the key to turbocharging your code's performance.

Think about it: using a hash table can turn a sluggish search operation into a lightning-fast retrieval. Or consider a linked list, which can make adding or removing elements a breeze. It's like having a high-speed train instead of a horse cart for your data.

Solve Problems Like a Pro:

Data structures are your Swiss Army knife for tackling complex challenges. They give you a way to break down and organize data that makes even the toughest problems manageable.

Need to map out a hierarchy? Trees have got your back. Dealing with networked data? Graphs are your go-to. It's about having the right tool for the job.

Flexibility at Your Fingertips:

The beauty of data structures lies in their variety. Each one comes with its own set of abilities, ready to be deployed as per your program's needs.

This means you can tailor your approach to fit the task at hand, making your software more adaptable and robust. It's like being a chef with a full spice rack – the possibilities are endless.

Optimize Memory:

In the world of programming, memory is gold, and data structures help you spend it wisely. They're the architects of memory, building and managing it efficiently.

Dynamic arrays, for example, are like expandable storage units, growing and shrinking as needed. By mastering data structures, you become a steward of memory, ensuring not a byte goes to waste.

Scale Up Without Breaking a Sweat:

As your software grows, so do its demands. This is where data structures come into their own. They're built for scale.

Balanced binary search trees, for instance, excel at managing large datasets, keeping searches and sorting fast no matter the size. Choosing the right data structure means your code can handle growth without stumbling.

Key Takeaways

Data structures are the pillars that support great programming. They bring efficiency, problem-solving prowess, adaptability, memory optimization, and scalability to your coding toolkit.

Understanding and utilizing them is not just a skill – it's a game changer in the world of programming. Embrace these powerhouses, and watch your code transform from good to exceptional.

12. How to Choose the Right Data Structure for Your Application

Selecting the right data structure is a pivotal decision in software development, one that directly influences your application's efficiency, performance, and scalability.

It's not just about choosing a tool – it's about aligning your code with the demands of your project for optimal functionality. Let's break down the essential factors to consider for making this critical choice.

Clarify Your Application's Needs

The first step is understanding your application's specific requirements. What kind of data are you dealing with? What operations will you perform? Are there any constraints?

For instance, if fast search is a priority, certain structures like hash tables might be ideal. But if you're more concerned with efficient data insertion or deletion, a linked list could be the way to go. It's about matching the data structure to your unique needs.

Analyze Time and Space Complexity

Every data structure comes with its own set of complexities. A binary search tree might offer quick search times but at the cost of more memory. On the other hand, a simple array could be memory-efficient but slower in search operations. Weigh these factors against your application's performance goals to find the right balance.

Forecast Data Size and Growth

How much data will your application handle, and how might this change over time? For small or static data sets, simple structures might suffice. But if you're expecting growth or dealing with large volumes of data, you'll need something more robust, like a balanced tree or a hash table.

Anticipating your data's trajectory is key to choosing a structure that won't just work today but will continue to perform as your application grows.

Evaluate Data Access Patterns

How will you access your data? Sequentially or randomly? The answer to this question can greatly influence your choice. Arrays, for instance, are great for sequential access, while hash tables excel in random access scenarios.

Understanding your access patterns helps you pick a structure that optimizes your most frequent operations.

Mind Memory Constraints

Finally, consider the memory environment of your application. Some data structures are more memory-intensive than others. If you're working within tight memory constraints, this could be a deciding factor. Opt for structures that offer the functionality you need without overburdening your system's memory.

Key Takeaways

In summary, choosing the right data structure is about understanding your application's unique requirements and aligning them with the strengths and limitations of different structures. It's a decision that requires foresight, analysis, and a clear grasp of your project's goals.

With these considerations in mind, you're well-equipped to make a choice that enhances your application's performance and scalability.

13. How to Efficiently Implement Data Structures

In the world of software engineering choosing and using data structures efficiently can make or break your system's performance. Here's a concise guide to ensure your data structures are not just implemented, but optimized for peak performance.

Select the Right Tool for the Job

A chef picks a knife or a blender depending on what they're making. Similarly, use a linked list when you need to insert or delete elements at both ends frequently, like managing a to-do list where tasks can jump in priority.

An array is great for a static list of high scores in a game, but a hash table shines when developing a contact book app where quick retrieval of a contact's details is crucial.

Understand the Cost of Your Choices

Consider space-time trade-offs. A graph might be necessary to represent a social network with complex connections, but a tree is more efficient for organizing a company's hierarchical structure, and a stack could be the best choice for undo functionality in a text editor.

Code with Clarity and Standards

It's like writing a recipe that others can follow easily. Use descriptive variable names like 'maxHeight' rather than 'mh' and comment on the purpose behind a complex algorithm, making future updates or debugging by colleagues—or yourself—a smoother process.

Prepare for the Unexpected

Error handling is like having insurance – it might seem unnecessary until it's not. Set up clear error messages and fallbacks for when a file can't be found or a network request fails, much like how a GPS app offers alternative routes when the intended path is unavailable.

Manage Memory Meticulously

It's like keeping a kitchen tidy while cooking. Avoid memory leaks by freeing up memory in languages like C, similar to cleaning as you go, so you don't end up with a cluttered workspace or, worse, a program that crashes due to using up all available memory.

Test, Then Test Some More

It's like proofreading an article multiple times before publishing. Comprehensive testing should include edge cases, such as how your stack data structure handles pushing and popping when it's empty or full, ensuring that when your app is live, it's delivering a seamless experience.

Never Stop Optimizing

Continuously refine your code like an editor polishes a manuscript. Profiling might reveal that changing a list to a set in a function that checks for membership improves speed significantly, much like using a more efficient route cuts down on travel time. Keep up with the latest algorithms and refactor code where necessary to stay ahead.

Key Takeaways

Mastering data structures is about making informed choices, writing clear and maintainable code, preparing for the unexpected, managing resources wisely, and committing to continuous testing and optimization. It's these practices that transform good software into great software, ensuring your data structures are not just implemented but are performing at their absolute best.

14. How to Optimize for Performance: Understanding Time Complexities in Data Structures

In the world of computer science, data structures are more than just storage mechanisms—they are the architects of efficiency. Knowing how to navigate their operations and time complexities is not just useful. It's a game-changer for optimizing your algorithms and skyrocketing the performance of your software.

Let's break down the most common operations and their time complexities.

Insertion: (O(1) to O(n))

Insertion is like adding a new player to your team. Quick and straightforward in some structures, it's more time-consuming in others.

For instance, adding an element to the start of a linked list is a swift O(1) operation. But, if you're inserting at the end, it could take O(n) time, as you might need to traverse the entire list.

Deletion: (O(1) to O(n))

Think of deletion as removing a puzzle piece. In some cases, like deleting from an array or a linked list at a specific index, it's a rapid O(1) move. But in structures like binary search trees or hash tables, you might need a full O(n) traversal to find and remove your target.

Searching: (O(1) to O(n))

Searching is like trying to find a needle in a haystack. In an array or hash table, it's often a lightning-fast O(1) process. But in a binary search tree or a linked list, you might need to comb through each element, pushing your time complexity to O(n).

Access: (O(1) to O(n))

Accessing data is like picking a book from a shelf. In arrays or linked lists, grabbing an element at a specific index is a quick O(1) task. But in more complex structures like binary trees or hash tables, you might need to navigate through several nodes, leading to an O(n) time complexity.

Sorting: (O(n log n) to O(n²))

Sorting is all about putting your ducks in a row. The efficiency varies widely based on the algorithm you choose.

Classics like Quicksort, Mergesort, and Heapsort generally operate in the O(n log n) range. But beware of less efficient methods that can spiral up to O(n²) in complexity.

Key Takeaways

Understanding these time complexities is key when choosing which data structure to use. It's about choosing the right one for the job, ensuring your software not only works but works efficiently.

Whether you're building a new application or optimizing an existing one, these insights are your roadmap to a high-performance solution.

15. Real-World Examples of Data Structures in Action

Data structures are not just theoretical concepts; they are the silent powerhouses behind many of the technologies we use daily. Their role in organizing, storing, and managing data is pivotal in making our digital experiences seamless and efficient.

Let's explore how these unsung heroes of the tech world make a real impact in various applications.

Undo Feature in Text Editors:

Ever hit 'undo' in a text editor and marveled at how it retrieves your last action? That's a stack data structure at work. Each action you take is 'pushed' onto the stack. Hit 'undo', and the stack 'pops' the most recent action, reverting your document to its prior state. Simple, yet ingenious.

Social Networking Platforms:

Platforms like Facebook and Twitter are not just about connecting people – they're about managing colossal data networks. Here, graph data structures come into play. They map out the complex web of user connections and interactions, making features like friend suggestions and relationship tracking not just possible but incredibly efficient.

GPS Navigation Systems:

Ever wondered how your GPS calculates the quickest route? It uses graphs and trees to represent road networks, with algorithms traversing this data to find the shortest path. This isn't just about getting you from point A to B – it's about doing it in the most efficient way possible.

E-commerce Recommendation Engines:

When an online store seems to read your mind with perfect product suggestions, thank data structures like hash tables and trees. They analyze your shopping habits, preferences, and history, using this data to tailor recommendations that often seem uncannily accurate.

File System Organization:

Your computer's ability to store and retrieve files swiftly is courtesy of data structures. Trees help in organizing directories, making file navigation a breeze. Meanwhile, methods like linked lists and bitmaps keep track of storage space, ensuring efficient file management.

Search Engine Indexing:

The speed at which search engines like Google deliver relevant results is all thanks to data structures. Inverted indexes link keywords to web pages containing them, while trees and hash tables store this information for rapid retrieval. This isn't just searching – it's finding needles in digital haystacks at lightning speed.

16. Essential Toolkit for Learning Data Structures

Navigating the world of data structures can be daunting, but the right resources and tools can transform this journey into an enlightening experience.

Whether you're starting out or looking to deepen your expertise, the following curated resources are your allies in mastering the art of data structures.

• freeCodeCamp: An open-source community where you can learn to code for free. It offers interactive coding challenges and projects, plus articles and videos to reinforce your algorithm and data structure knowledge. Bingo!
• "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein: This seminal book is a treasure trove of algorithmic wisdom, offering a deep dive into the principles and techniques of data structures.
• "Data Structures and Algorithms: Annotated Reference with Examples" by Granville Barnett and Luca Del Tongo: A practical guide that demystifies data structures with clear explanations and real-world examples, perfect for self-learners.
• Coursera: A hub for top-tier online courses from renowned universities, offering structured learning paths and practical assignments to solidify your understanding of data structures and algorithms.
• VisuAlgo: Bringing data structures to life with animated visualizations, this tool simplifies complex concepts, making them more accessible and understandable.
• Data Structure Visualizations: A platform that offers interactive visual representations, allowing you to explore and understand the mechanics of common data structures.
• LeetCode: A vast repository of coding challenges, including data structure-specific problems, to refine your coding skills in a real-world context.
• HackerRank: With its extensive array of challenges, this platform is an excellent arena for applying and honing your data structure implementation skills.
• Stack Overflow: Tap into the collective wisdom of a vast community of programmers, a valuable resource for troubleshooting and gaining insights from seasoned developers.
• Reddit: Discover programming communities where discussions on data structures thrive, offering study group opportunities and resource recommendations.

These resources are more than just learning aids – they are gateways to a deeper understanding and practical application of data structures. Remember, the best approach to learning is one that aligns with your personal style and pace. Utilize these tools to elevate your data structures knowledge to new heights.

17. Conclusion and Actionable Steps Forward

Armed with a comprehensive grasp of data structures, you're now poised to leverage their full potential. Here are key takeaways and actionable steps to guide your ongoing journey:

Practice and Experiment

Apply your knowledge by implementing various data structures across different programming languages. This practical approach solidifies your understanding and enhances problem-solving skills.

Explore Advanced Structures:

Venture beyond the basics into more complex data structures like trees, graphs, and hash tables. Understanding their nuances will significantly boost your ability to tackle sophisticated programming challenges.

Deep Dive into Algorithms:

Pair your data structure knowledge with a study of algorithms. Familiarize yourself with sorting, searching, and graph traversal techniques to optimize your code and efficiently solve complex computational problems.

Stay Informed and Engaged:

Keep abreast of the ever-evolving software engineering landscape. Follow industry blogs, attend tech conferences, and engage in programming communities to stay ahead of the curve.

Collaborate and Share:

Join forces with peers in development communities. Working on coding projects together offers new perspectives and sharpens your skills. Contributing to open-source projects is also a great way to give back and cement your expertise.

Showcase Your Skills:

Build a portfolio that highlights your proficiency in using data structures to solve real-world problems. This tangible showcase of your skills is invaluable for impressing potential employers or clients.

Embrace the journey of mastering data structures. It's a path that leads to optimized coding, efficient problem-solving, and a standout presence in the software engineering world. Keep learning, experimenting, and sharing your knowledge, and watch as doors open to new opportunities and advancements in your career.

18. Conclusion

In summary, learning how to use data structures is a cornerstone for any aspiring software engineer. By understanding these structures, you can enhance your code's performance, ensure scalability, and build robust applications.

From fundamental arrays and linked lists to complex trees and graphs, each structure offers unique benefits and applications.

Continue your exploration by delving into algorithms and their practical implementations. Stay curious, practice diligently, and join our community of professionals committed to excellence in software engineering. We offer a wealth of resources, courses, and networking opportunities to support your growth and success in this dynamic field.

Resources

If you're keen on mastering data structures, check out LunarTech.AI's Data Structures Mastery Bootcamp. It's perfect for those interested in AI and machine learning, focusing on effective use of data structures in coding. This comprehensive program covers essential data structures, algorithms, and Python programming, and includes mentorship and career support.

Additionally, for more practice in data structures, explore these resources on our website:

1. Java Data Structures Mastery - Ace the Coding Interview: A free eBook to advance your Java skills, focusing on data structures for enhancing interview and professional skills.
2. Foundations of Java Data Structures - Your Coding Catalyst: Another free eBook, diving into Java essentials, object-oriented programming, and AI applications.

Visit our website for these resources and more information on the bootcamp.

Connect with Me:

• Follow me on LinkedIn for a ton of Free Resources in CS, ML and AI
• Visit my Personal Website
• Subscribe to my The Data Science and AI Newsletter

About the Author

Vahe Aslanyan here, at the nexus of computer science, data science, and AI. Visit vaheaslanyan.com to see a portfolio that's a testament to precision and progress. My experience bridges the gap between full-stack development and AI product optimization, driven by solving problems in new ways.

With a track record that includes launching a leading data science bootcamp and working with industry top-specialists, my focus remains on elevating tech education to universal standards.

As we wrap up the 'Data Structures book', I extend my gratitude for your time. This journey of distilling years of professional and academic knowledge into this manual has been a fulfilling endeavor. Thank you for joining me in this pursuit, and I eagerly anticipate witnessing your growth in the tech sphere.

I'd recommend the set data structure. It's an unordered collection of unique elements, meaning it cannot contain any duplicate items.

When you add elements to a set, Python automatically removes any duplicates. This makes it a perfect choice for scenarios where you need to store a collection of items while ensuring uniqueness.

How to Use a set in Python

You can create a set in Python using curly braces {} or the built-in set() function.

Suppose, you already know that you would have duplicate items but you do not want to keep the duplicate items at all. Then you can start directly entering the items in a set. Here's an example:

# Creating a set
my_set = {1, 2, 3, 4, 3, 5}  # Duplicate '3' is automatically removed

print(my_set)  # Output: {1, 2, 3, 4, 5}

Here I have created a set in the my_set variable, and I have 2 duplicate items there. As you can see in the output, the duplicates have been removed.

If you have a list with potential duplicates and want to remove them to create a set, you can simply convert the list to a set using the set() function.

Suppose, you already have a list containing a lot of data – let's say it contains the data of your shop's customers. Now at the end of the month, you want to know exactly how many individual customers arrived at your shop's doorstep.

During the month, you stored the customer's unique IDs in a list and recorded it each time they visted your shop. As some customers came more than once in that month, it is highly possible that the list where you stored the customer IDs has duplicate data (which is redundant when you're trying to calculate all unique customers).

So you want a solution where you only extract the unique customer ID from that particular list – but for safety, you do not want to modify or change the original list data.

In that case, you can simply create a new variable to extract the unique data from that list and store it there. You can use the set functionality here as well. For example:

# Removing duplicates from a list and creating a set
my_list = [1, 2, 2, 3, 4, 4, 5]
my_set = set(my_list)

print(my_set)  # Output: {1, 2, 3, 4, 5}

Here, I have my list in the my_list variable which currently has duplicate items in it – 2 (appears twice) and 4 (also appears twice).

But, in the second line, I have initialized a new variable named my_set where I store the set of my_list. As the set automatically removes any duplicates and keeps only a single item from the duplicates, I am storing all the unique items in my my_set variable.

But if I print my_list, I will still get the duplicate values altogether. This is because we have not changed the original list at all. We simply created a new variable named my_set and stored only the unique values from that list.

But if you really want to remove the duplicates from the original list and create another list, then you can remove the duplicates from the list by first changing it to a set and then back to a list again. In that way, you can get a new list with the duplicates removed.

For example:

my_list = [1, 2, 2, 3, 4, 4, 5]
new_list = list(set(my_list)) # Removing duplicates by first changing to a set and then back to a list
print(new_list) # Output: [1, 2, 3, 4, 5]

But if you really want to modify the original list, then you can create a set and remove the duplicates, and then you can again change that to a list and store the list data to the original list again!

my_list = [1, 2, 2, 3, 4, 4, 5]
my_list = list(set(my_list)) # Altering the list to remove duplicates from the earlier list data and storing the new data without duplicates in that list 
print(my_list) # Output: [1, 2, 3, 4, 5]

Sets provide fast membership testing and efficient operations for set theory operations (like union, intersection, and difference), which makes them a great choice for handling collections of unique elements in Python.

📺 Video Walkthrough

I know that many of you like to watch a video instead of following a complete article. Fear not! I have also created a complete video tutorial for you:

Conclusion

I hope you have enjoyed this short article.

If you have any questions then please let me know by reaching out on Twitter or LinkedIn.

You can also follow me on:
🎁GitHub: FahimFBA
🎁YouTube: @FahimAmin

If you are interested then you can also check my website: https://fahimbinamin.com/

Indexing in PostgreSQL is a process that involves creating data structures that are optimized to efficiently search and retrieve data from tables.

An index is a copy of a portion of a table, arranged in a way that enables PostgreSQL to quickly locate and retrieve rows that match a particular query condition.

When a query is executed, PostgreSQL looks at the indexes available to determine if any of them can be used in satisfying the query condition. If it finds a relevant index, PostgreSQL employs it to quickly identify the corresponding rows in the table. This results in significantly speedy queries, especially in situations where tables are large or the conditions are complex.

PostgreSQL provides support for several index types, including B-tree, hash, GiST, SP-GiST, and BRIN. Each index type is tailored to cater to distinct query types and data access patterns.

Apart from the standard index types, PostgreSQL permits users to define custom indexes utilizing user-defined functions.

It's important to note that creating an index requires additional disk space and can impact the performance of write operations, such as INSERT, UPDATE, and DELETE. Because of this, it's essential to consider the trade-offs and carefully choose which columns to index based on the queries you frequently execute and the access patterns of your data.

B-tree Index

B-tree index is the most commonly used type of index to efficiently store and retrieve data in PostgreSQL. It's the default index type. Whenever we use the CREATE INDEX command without specifying the type of index we want, PostgreSQL will create a B-tree index for the table or column.

A B-tree index is organized in a tree-like structure. The index starts with a root node, with pointers to child nodes. Each node in the tree typically contains multiple key-value pairs, where the keys are used for indexing, and the values point to the corresponding data in the table.

To create a B-tree index in PostgreSQL, use the CREATE INDEX statement. Here’s the syntax:

CREATE INDEX index_name ON table_name;

Single-column indexing

To create a single B-tree index based on one table column instead of creating an index on the entire table, the syntax is as follows.

CREATE INDEX index_name ON table_name (column_name);

index_name is the name you want to give to the index.

table_name is the name of the table on which you want to create the index.

column_name is the name of the column(s) on which you want to create the index.

Example:

Let’s create a table called “sales_info” and insert some dummy data.

CREATE TABLE sales_info (
  sales_id integer NOT NULL, email VARCHAR, 
  location VARCHAR, item_purchased VARCHAR, 
  price VARCHAR
);

Insert values into the table using the INSERT statement:

INSERT INTO sales_info (
  sales_id, email, location, item_purchased, 
  price
) 
VALUES 
  (
    1, 'halie46@gmail.com', 'London', 
    'Headphone', '$50'
  ), 
  (
    2, 'romaine21@gmail.com', 'Australia', 
    'Webcam', '$50'
  ), 
  (
    3, 'frederique19@gmail.com', 'Canada', 
    'iPhone 14 pro', '$1259'
  ), 
  (
    4, 'kenton_macejkovic80@hotmail.com', 
    'London', 'Wireless Mouse', '$20'
  ), 
  (
    5, 'alexis62@hotmail.com', 'Switzerland', 
    'Dell Charger', '$15'
  ), 
  (
    6, 'concepcion_kiehn@hotmail.com', 
    'Canada', 'Longitech Keyboard', 
    '$499'
  );

If we create a B-tree index on the sales_id column by running this statement:

CREATE INDEX idx_sales_id ON sales_info (sales_id);

When we run the SELECT statement, we get the total query runtime below.

The time displayed might look insignificant, as the table we are working with is small. But when working with a large amount of data, this will significantly improve the performance of your queries.

To learn more about the B-Tree index and the behaviors of B-Tree operator classes, see the official documentation here.

Hash Indexes

Hash indexes are designed for fast key-value lookups. When a query condition requires equality checks on indexed columns, hash indexes can provide extremely fast retrieval, as the hash function directly determines the location of the desired data. Hash indexes are most suitable for equality comparisons, such as = or IN operations.

Like other index types, hash indexes need to be maintained during data modifications (inserts, updates, and deletes) to ensure data consistency. But hash index maintenance can be more expensive than B-tree indexes due to the need to resolve collisions and rehash data.

To create a hash index in PostgreSQL, you can use the CREATE INDEX statement with the USING HASH clause. For example:

CREATE INDEX hash_name ON table_name USING HASH (column_name);

This statement creates a hash index named "hash_name" on the specified column of the table.

Point to note here: while hash indexes are available in PostgreSQL, they are not suitable for range queries or sorting. B-tree indexes are typically preferred for such scenarios. Again, B-tree indexes are the default and commonly used index type.

Hash indexes have specific use cases and limitations, and it's essential to assess your requirements and query patterns before deciding on the appropriate index type for your PostgreSQL database.

Example:

Create a Hash index on the table sales_info using HASH for the column sales_id:

CREATE INDEX idx_sales_id ON sales_info USING HASH(sales_id);

Select and filter the data using the WHERE clause:

EXPLAIN (ANALYZE) 
Select 
  * 
from 
  sales_info 
WHERE 
  sales_id = 5;

Check out the official documentation if you want to dive deeper into Hash Indexes.

GiST and SP-GiST Indexes

GiST (Generalized Search Tree) and SP-GiST (Space-Partitioned Generalized Search Tree) indexes are advanced index types in PostgreSQL that provide support for a wide range of data types and search operations.

They are particularly useful for handling complex data structures and spatial data, GiST indexes are what you use if you want to speed up full-text searches.

Creating GiST and SP-GiST Indexes:

To create a GiST or SP-GiST index in PostgreSQL, you can use the CREATE INDEX statement with the USING GIST or USING SPGIST clause, respectively.

Here's an example of creating a GiST index on a geometry column:

CREATE INDEX index_geometry ON table_name USING GIST (geometry_column);

And here's an example of creating an SP-GiST index on a tsvector column:

CREATE INDEX index_text_search ON table_name USING SPGIST (tsvector_column);

Here's an overview of GiST and SP-GiST indexes in PostgreSQL:

GiST Index:

• Generalized Search Tree (GiST) indexes are versatile index structures that support various data types beyond simple scalar values.
• GiST indexes enable efficient searching and retrieval for complex data structures such as geometric objects, text documents, arrays, and more.
• They are based on the concept of multidimensional trees, allowing for flexible search operations.
• GiST indexes can handle different search predicates, including equality, range, and spatial operations like overlaps, containment, and distance-based searches.

SP-GiST Index:

• Space-Partitioned Generalized Search Tree (SP-GiST) indexes are an extension of GiST indexes that further enhance indexing capabilities.
• SP-GiST indexes are designed for data types with space-filling characteristics, such as multi-dimensional data, time-series data, and network data.
• They partition the index space into non-overlapping regions, optimizing search performance for specific access patterns.
• SP-GiST indexes provide support for various data types, including geometric objects, text search, and more.
• They are particularly efficient for spatial indexing and can handle complex spatial queries, including intersection, nearest-neighbor, and clustering operations.

See the official documentation GiST and SP-GiST indexes for more information.

BRIN Indexes

BRIN, or Block Range Index, is an index type in PostgreSQL designed to provide efficient indexing for large tables with sorted data. BRIN index contains the minimum and maximum in a group of database pages.

BRIN index makes is the easiest way to optimize for speed. It is particularly useful for data that exhibits sequential or sorted characteristics, such as time series data or data with a natural ordering.

Here’s an overview of the BRIN Index:

• BRIN indexes divide the table into logical blocks and store summary information about each block.
• Each block contains a range of values, and the index stores the minimum and maximum values within each block.
• Instead of storing individual index entries for each row, BRIN indexes store block-level summaries, making them smaller in size compared to other index types.
• BRIN indexes work well when the data is sorted or when sequential scans are more efficient than index scans.

To create a BRIN index in PostgreSQL, you use the CREATE INDEX statement with the USING BRIN clause.

Here's an example of creating a BRIN index on a timestamp column:

CREATE INDEX timestamp ON table_name USING BRIN (column);

The above statement creates a BRIN index on the specified timestamp column of the table.

Here are some things to consider when creating a BRIN Index:

• BRIN indexes are most effective when the data is sorted or exhibit natural ordering.
• They may not be suitable for tables with highly unsorted or non-sequential data.
• BRIN indexes are generally used for read-intensive workloads where sequential scans are prevalent.
• Regular maintenance and periodic reindexing may be necessary to ensure optimal performance.

To read more on BRIN Indexes, you can check out the official documentation.

Conclusion

In this quick guide, we have seen other types of indexes supported by PostgreSQL other than the B-Tree index.

It is not recommended to create an index on the fly just before running a one-off query. Creating a well-designed index requires careful planning and testing.

It's important to consider that indexes consume disk space. Also, whenever new data rows are inserted or existing rows are updated, the database automatically updates the corresponding index entries.