Dynamic Data Structures: From Arrays to Linked Lists

I started learning programming with Python, and when I first learned about lists, I was thrilled because I could build so many things with them and had plenty of tricks to experiment with. I began by creating simple terminal restaurant programs and felt really good about myself.

Python lists are like flexible arrays. When I first started programming with Python and learned about lists, I didn't realize that I was actually using flexible arrays. I thought that lists were a more powerful version of arrays that let me change the size as needed.

Later, I learned that Python lists were actually flexible arrays. With flexible arrays, we can add or remove elements and change the size of the array. This makes them more flexible than arrays, which always have the same size.

Flexible arrays are important in computer programming. They help us organize and manage data in a useful way. We can create more powerful and flexible data structures that can change and grow as needed. In this article, I am gonna be talking about some of the dynamic data structures.

What is an array?

An array is a commonly used data structure in computer programming. It is a collection of elements of the same data type that are stored in contiguous memory locations. Arrays are a static data structure, meaning that their size is fixed and cannot be changed during runtime.

For example, let's say I want to keep a record of every beer brand I consume throughout the year.

One solution could be brute-forcing the storage by creating 365 individual variables, such as BeerBrand11, BeerBrand2, BeerBrand3, and so forth. However, this would be tedious to type and would not allow for any structure in the data. For instance, BrandDay2 is only a textual tag, so the program would not recognize that BrandDay1 stores information for the day before and BrandDay3 for the day after.

Arrays can be helpful for storing multiple values in adjacent and indexable bins. For instance, if you wanted to keep a record of every beer brand you consumed throughout the year, you could use an array. This would be more efficient than creating individual variables for each brand, as you could store all the brands in one place and easily access them by their index in the array.

How a zero-indexed array is arranged in computer memory?

When an array is created, it is allocated a contiguous block of memory, and each element of the array is stored at a specific memory address within the block.

In a zero-indexed array, the first element is located at the memory address of the array itself. The second element is located at the memory address of the array plus the size of one element, which is determined by the data type. The third element is located at the memory address of the array plus the size of two elements, and so on.

int numbers[5] = {1, 2, 3, 4, 5};

The memory addresses and values of each element in the array would be arranged as follows:

As you can see, the first element of the array is located at memory address 0x1000, which is the address of the array itself. The remaining elements are located at memory addresses that are offset from the address of the array by the size of one element.

This allows the computer to quickly access any element in the array by calculating its memory address based on the index and the size of one element. It also ensures that the elements are stored in contiguous memory locations, which can improve memory access times and cache performance.

To find the position of an element in an array, use this formula:

location_of_element = address_of_array + (index * size_of_one_element)

The thing about arrays is that they have fixed sizes, meaning that they cannot change during runtime. This makes it hard to add or remove elements from them. For instance, if you have an array of size 10 and want to add an 11th element, you must create a new array with a bigger size and copy all the existing elements to it. This process can consume time and memory, particularly if the array is large. Similarly, if you want to remove an element from an array, you need to shift all the elements after the deleted element to fill the gap. This can also be time-consuming, especially if the array is big.

Dynamic Data Structure

To meet this need for dynamic data structures, many modern programming languages offer dynamic “arrays” that grow and shrink as you add elements, such as Python's list and JavaScript's Array.

These data structures are implemented as linked lists or vectors, which allow for efficient resizing and element insertion. Other dynamic data structures include stacks, queues, and trees, which can be useful for a variety of applications.

Array List

An array list is like an array that can change size. It starts with a fixed size, but when it gets full, it automatically gets bigger to fit more stuff. This is better than a regular array for big sets of data that need to change size a lot.

Similar to arrays they provide instant access to elements. This means that you can quickly retrieve and modify elements at any position in the array list. Array lists can also be used to implement other dynamic data structures like stacks, queues, and trees.

Another advantage of array lists is that they can be more memory-efficient than linked lists, which is another type of dynamic data structure (which I will discuss later in this article). Linked lists require extra memory to store pointers or references to the next element in the list, while array lists only require memory to store the elements themselves. This can make array lists a good choice when memory usage is a concern.

However, there are also some downsides to using array lists. One major disadvantage is that inserting or removing elements in the middle of the list can be slow since all the elements after the insertion or removal point need to be shifted over to make room for the new element or fill the gap. This can be especially slow if the array list is large.

Another disadvantage is that array lists have a fixed capacity, which means that they can run out of space if you try to add too many elements. In this case, you would need to create a new array list with a larger capacity and copy over all the existing elements.

To solve the problem of limited space in array lists, you can use a resizing method called array doubling. When the array list is full, a new array with twice the capacity is made, and all the elements from the old array are moved to the new one. This lets the array list keep growing without running out of room.

It might seem a bit odd to create an array list in a dynamic language like JavaScript, but the code below can give you an idea of how to create such a data structure.

class ArrayList {
  constructor() {
    this.length = 0;
    this.data = {};
    this.capacity = 1;
  }

  push(value) {
    if (this.length === this.capacity) {
      this._resize(2 * this.capacity);
    }
    this.data[this.length] = value;
    this.length++;
  }

  pop() {
    if (this.length === 0) {
      return undefined;
    }
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    if (this.length === this.capacity / 4) {
      this._resize(this.capacity / 2);
    }
    return lastItem;
  }

  get(index) {
    return this.data[index];
  }

  delete(index) {
    const item = this.data[index];
    this._collapseTo(index);
    return item;
  }

  _collapseTo(index) {
    for (let i = index; i < this.length; i++) {
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length - 1];
    this.length--;
    if (this.length === this.capacity / 4) {
      this._resize(this.capacity / 2);
    }
  }

  _resize(newCapacity) {
    const newData = {};
    for (let i = 0; i < this.length; i++) {
      newData[i] = this.data[i];
    }
    this.data = newData;
    this.capacity = newCapacity;
  }
}

The push, pop, delete, and _collapseTo methods are like the ones in the previous version, but they also make sure to check if the array list needs to be made bigger based on how much data it's currently holding.

Pointers and References

One thing that confused me during my time at university was pointers, especially when working on Arduino projects. A pointer is a variable that stores only the addresses in the computer’s memory. What is the purpose of a variable that simply points to another location in memory? Why do you always have to make things so complicated? I admit it I was bad.

For example, let's say you are writing a program that needs to sort a large array of numbers. If you pass the entire array as an argument to a sorting function, the program needs to make a copy of the entire array in memory, which can be slow and memory-intensive. However, if you pass a pointer to the array instead, the sorting function can manipulate the original array directly, which can be much faster and more memory-efficient.

This article will be about t they can be used as a powerful mechanism for chaining multiple elements together, effectively creating a linked list. We will explore the different types of linked lists, such as singly linked lists, doubly linked lists, and circular linked lists, and examine their strengths and weaknesses.

Linked List

Linked lists are the simplest example of a dynamic data structure and are a close cousin to arrays. Like arrays, they are a data structure for storing multiple values. Unlike arrays, linked lists are composed of a chain of nodes linked together by pointers.

A basic node in a linked list is a composite data structure containing two parts:

• a value (of any type)
• a pointer to the next node in the list

Another real-life example of a linked list is a music playlist. Each song in a playlist is a node in a linked list. Each song has a value (the song title and artist) and a pointer to the next song in the playlist. You can add or remove songs from the playlist without affecting the other songs. This makes a linked list a good choice for situations where you need to add or remove items from a list frequently.

interface Node<T>{
	value: T;
	next: Node
}

In a linked list, the nodes don't have to be next to each other in memory. Instead, each node is connected to the next node using a pointer. This makes a chain of nodes that can be looked at one by one. Because the nodes in a linked list are not always next to each other in memory, linked lists are better for adding or removing things quickly.

Traversing a linked list

To traverse a linked list, you start at the head node and follow the next pointers until you reach the end of the list.

function traverseLinkedList(head) {
  let currentNode = head;
  while (currentNode !== null) {
    console.log(currentNode.value);
    currentNode = currentNode.next;
  }
}

This function goes through each item in a linked list and prints out what's in it. To start, we look at the first item, and then we keep looking at the next item until we reach the end of the list. Going through a linked list takes longer as the list gets longer. We can't just go straight to an item like with an array.

We have to start at the beginning and follow the next pointers until we reach the item we want. Accessing an item in a linked list is an O(n) operation, where n is the number of items in the list. This means that if we have a linked list with 1,000 items, it could take up to 1,000 operations to find the item we want. However, linked lists are still useful in situations where we need to frequently add or remove items, because adding or removing an item is an O(1) operation, regardless of the size of the list.

Inserting an element to a linked list

To add something to a linked list, we need to create a new node, set its value, and update the pointers of the nodes around it. Here's how we do it:

• Create a new node with the value we want to insert.
• Set the next property of the new node to point to the node that comes after it in the list.
• Update the next property of the node that comes before it in the list to point to the new node.

insertAt(value: string, index: number) {
    if (this.length < index) return new Error("Cannot inset at that index");
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    let newNode = new LinkNode(value);
    newNode.next = current.next;
    current.next = newNode;
    this.length += 1;
  }

Deleting an element from a linked list

To delete an element from a linked list, we need to update the pointers of the nodes around it. Here's how we do it:

• Find the node that comes before the node we want to delete.
• Set the next property of the node that comes before it to point to the node that comes after it.
• Set the next property of the node we want to delete to null.

deleteAt(index: number) {
    if (this.length < index) return new Error("Cannot delete at that index");
    let current = this.head;
    for (let i = 0; i < index - 1; i++) { // we need to find the node before the one we want to delete
      current = current.next;
    }
    current.next = current.next.next;
    this.length -= 1;
  }

Doubly Linked List

A doubly linked list is a type of linked list where each node has two pointers: one to the next node and one to the previous node. This allows for more efficient traversal in both forward and backward directions.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

Time and Space Complexity of Linked Lists

Linked List in Typescript

class Node {
  value: string;
  next: Node;
  constructor(value: string) {
    this.value = value;
  }
}
class LinkedList {
  head: Node;
  length: number;
  constructor() {
    this.head = null;
    this.length = 0;
  }
  add_front(value: string) {
    let newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.length += 1;
    return newNode;
  }
  add_back(value: string) {
    let newNode = new Node(value);
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
    this.length += 1;
  }
  getNodes() {
    let arr: string[] = [];
    let current = this.head;
    for (let i = 0; i < this.length; i++) {
      arr.push(current.value);
      current = current.next;
    }
    console.log(arr);
    return arr;
  }
  getByValue(value: string): Node | Error {
    let current = this.head;
    while (current.next) {
      if (current.value === value) {
        return current;
      }
      current = current.next;
    }
    return new Error("item not exists");
  }
  insertByIndex(index: number, value: string) {
    if (this.length < index) return new Error("Insert is impossible");
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    let newNode = new Node(value);
    newNode.next = current.next;
    current.next = newNode;
    this.length += 1;
  }
  insertBehindValue(target: string, value: string) {
    let current = this.head;
    while (current.next) {
      if (current.value === target) {
        let newNode = new Node(value);
        newNode.next = current.next;
        current.next = newNode;
        this.length += 1;
        return newNode;
      }
      current = current.next;
    }
  }
  deleteByValue(value: string) {
    let current = this.head;
    let prev = null;
    if (current.value === value) return current;
    while (current.next) {
      if (current.value === value) {
        if (prev) {
          prev.next = current.next;
        }
        this.length -= 1;
      }
      prev = current;
      current = current.next;
    }
  }
}

Related Articles