Understanding Linear Data Structures: Arrays, HashMaps, Sets, Lists, and Linked Lists

When developing programs we usually need to store data in memory, and the choice of data structure depends on how the data will be accessed. Common structures include Array, Map, Set, List, Tree, Graph, etc., and selecting the appropriate one can be challenging. This article aims to help you understand the performance of different data structures for reasonable usage.

The focus of this article is on linear data structures such as Array, Set, List, Stack, and Queue.

The table below summarizes the content discussed.

Bookmark, favorite, or share this article for future reference.

* = amortized runtime

Data Structure

Insert

Access

Search

Delete

Notes

Array

O(n)

O(1)

O(n)

O(n)

Inserting at the last position has complexity

O(1)

.

(Hash)

Map

O(1)*

O(1)*

O(1)*

O(1)*

Re‑hashing can affect insertion time.

Map

O(log(n))

-

O(log(n))

O(log(n))

Implemented with a binary search tree.

Set

(using HashMap)

O(1)*

-

O(1)*

O(1)*

Implemented via HashMap.

Set

(using List)

O(n)

-

O(n)

O(n)

Implemented with a List.

Set

(using Binary Search Tree)

O(log(n))

-

O(log(n))

O(log(n))

Implemented with a BST.

Linked List

(singly)

O(n)

-

O(n)

O(n)

Insertion or deletion at the head costs

O(1)

.

Linked List

(doubly)

O(n)

-

O(n)

O(n)

Insertion or deletion at head or tail costs

O(1)

; other positions cost

O(n)

.

Stack

(Array implementation)

O(1)

-

-

O(1)

Push and pop follow LIFO.

Queue

(simple Array implementation)

O(n)

-

-

O(1)

Enqueue uses Array.push, dequeue uses Array.shift (O(n)).

Queue

(improved Array implementation)

O(1)*

-

-

O(1)

Amortized O(1) for enqueue; dequeue is O(1) after occasional re‑balancing.

Queue

(List implementation)

O(1)

-

-

O(1)

Implemented with a doubly linked list.

Note: Binary search trees, other tree structures, and graphs will be discussed in another article.

Primitive Data Types

Integer: 1, 2, 3, …

Character: a, b, "1", "*"

Boolean: true, false

Floating point: 3.14159, 1.483e-2

Arrays consist of zero or more elements. Because arrays are easy to use and have excellent retrieval performance, they are one of the most common data structures.

Think of an array as a drawer where you store items in numbered compartments.

Array as a drawer

When you look for an element you can directly open the compartment (O(1)). If you forget which compartment holds the item, you must open each compartment sequentially (O(n)).

In dynamic languages such as JavaScript and Ruby, arrays can hold values of different types; in strongly typed languages like Java, C, or C++, you must declare length and type beforehand. JavaScript automatically expands the array when needed.

Array Built‑in Methods

Array methods differ slightly between languages. In JavaScript you can use unshift and push to add elements to the head or tail, and shift and pop to remove the first or last element.

Common JavaScript Array Functions

Function

Complexity

Description

array.

push

(element1[, …, elementN])

O(1)

Add one or more elements to the end.

array.

pop

()

O(1)

Remove the last element.

array.

shift

()

O(n)

Remove the first element.

array.

unshift

(element1[, …, elementN])

O(n)

Add one or more elements to the beginning.

array.

slice

([beginning[, end]])

O(n)

Return a shallow copy of the portion beginning to end (excluding end).

array.

splice

(start[, deleteCount[, item1[, …]]])

O(n)

Insert or delete elements.

Inserting Elements into an Array

There are many ways to insert elements. To add to the tail:

function insertToTail(array, element) {
  array.push(element);
  return array;
}
const array = [1, 2, 3];
console.log(insertToTail(array, 4)); // => [1,2,3,4]

The push operation has constant time complexity O(1) .

To add to the head:

function insertToHead(array, element) {
  array.unshift(element);
  return array;
}
const array = [1, 2, 3];
console.log(insertToHead(array, 0)); // => [0,1,2,3]

Because unshift shifts every existing element one position to make room, its complexity is O(n) .

The time complexity of Array.unshift is O(n) .

Accessing Elements in an Array

If you know the index, you can access the element directly in constant time:

function access(array, index) {
  return array[index];
}
const array = [1, 'word', 3.14, {a:1}];
access(array, 0); // => 1
access(array, 3); // => {a:1}

Array element access has time complexity O(1) .

Searching for an Element in an Array

If the element’s value is unknown, you must scan the array:

function search(array, element) {
  for (let index = 0; index < array.length; index++) {
    if (element === array[index]) {
      return index;
    }
  }
}
const array = [1, 'word', 3.14, {a:1}];
console.log(search(array, 'word')); // => 1
console.log(search(array, 3.14)); // => 2

Array linear search has time complexity O(n) .

Deleting Elements from an Array

Deletion can be performed by first locating the element and then using splice:

function remove(array, element) {
  const index = search(array, element);
  array.splice(index, 1);
  return array;
}
const array1 = [0,1,2,3];
console.log(remove(array1, 1)); // => [0,2,3]

The combined search ( O(n) ) and splice ( O(n) ) give an overall deletion cost of O(n) (constants are ignored).

HashMap Overview

A hash map maps keys to values using a hash function. A perfect hash function would map each distinct key to a distinct index, but in practice collisions occur.

Simple (naïve) HashMap implementation:

class NaiveHashMap {
  constructor(initialCapacity = 2) {
    this.buckets = new Array(initialCapacity);
  }
  set(key, value) {
    const index = this.getIndex(key);
    this.buckets[index] = value;
    return this;
  }
  get(key) {
    const index = this.getIndex(key);
    return this.buckets[index];
  }
  hash(key) { return key.toString().length; }
  getIndex(key) { return this.hash(key) % this.buckets.length; }
}

This naïve version suffers from many collisions because the bucket array is tiny and the hash function is weak.

Improving the Hash Function

Using the sum of character codes reduces collisions:

hash(key) {
  let hashValue = 0;
  const str = key.toString();
  for (let i = 0; i < str.length; i++) {
    hashValue += str.charCodeAt(i);
  }
  return hashValue;
}

Further improvement adds the character position (bit shifting):

hash(key) {
  let hashValue = 0;
  const str = `${key}`;
  for (let i = 0; i < str.length; i++) {
    hashValue += str.charCodeAt(i) << (i * 8);
  }
  return hashValue;
}

Including the type in the hash string eliminates collisions between different data types:

hash(key) {
  let hashValue = 0;
  const typeKey = `${key}${typeof key}`;
  for (let i = 0; i < typeKey.length; i++) {
    hashValue += typeKey.charCodeAt(i) << (i * 8);
  }
  return hashValue;
}

Decent HashMap with Collision Tracking

class DecentHashMap {
  constructor(initialCapacity = 2) {
    this.buckets = new Array(initialCapacity);
    this.collisions = 0;
  }
  set(key, value) {
    const index = this.getIndex(key);
    if (this.buckets[index]) {
      this.buckets[index].push({key, value});
      if (this.buckets[index].length > 1) this.collisions++;
    } else {
      this.buckets[index] = [{key, value}];
    }
    return this;
  }
  get(key) {
    const index = this.getIndex(key);
    const bucket = this.buckets[index] || [];
    for (const entry of bucket) {
      if (entry.key === key) return entry.value;
    }
  }
  hash(key) { /* same as improved version */ }
  getIndex(key) { return this.hash(key) % this.buckets.length; }
}

Testing shows that with an initial capacity of 2, collisions occur; increasing capacity to 10 reduces collisions; capacity 100 eliminates them.

Rehashing (Dynamic Resizing)

When the load factor exceeds a threshold (e.g., 0.75), the map doubles its capacity and re‑inserts all entries, reducing future collisions.

class HashMap {
  constructor(initialCapacity = 16, loadFactor = 0.75) {
    this.buckets = new Array(initialCapacity);
    this.loadFactor = loadFactor;
    this.size = 0;
    this.collisions = 0;
    this.keys = [];
  }
  set(key, value) {
    const {bucketIndex, entryIndex} = this._getIndexes(key);
    if (entryIndex === undefined) {
      const keyIdx = this.keys.push({content:key}) - 1;
      this.buckets[bucketIndex] = this.buckets[bucketIndex] || [];
      this.buckets[bucketIndex].push({key, value, keyIndex:keyIdx});
      this.size++;
      if (this.buckets[bucketIndex].length > 1) this.collisions++;
    } else {
      this.buckets[bucketIndex][entryIndex].value = value;
    }
    if (this.loadFactor > 0 && this.getLoadFactor() > this.loadFactor) {
      this.rehash(this.buckets.length * 2);
    }
    return this;
  }
  get(key) { /* similar to DecentHashMap */ }
  _getIndexes(key) { /* returns bucketIndex and entryIndex if found */ }
  rehash(newCapacity) {
    const newMap = new HashMap(newCapacity);
    this.keys.forEach(key => { if (key) newMap.set(key.content, this.get(key.content)); });
    this.buckets = newMap.buckets;
    this.collisions = newMap.collisions;
    this.keys = newMap.keys;
  }
  getLoadFactor() { return this.size / this.buckets.length; }
}

After inserting 12 items the load factor exceeds 0.75, triggering a rehash that doubles capacity from 16 to 32 and reduces collisions to zero.

HashMap Time Complexity Summary

Operation

Worst‑case

Average

Notes

Get / Search

O(n)

O(1)

Worst case when many collisions occur.

Set / Insert / Update

O(n)

O(1)

O(n) only when rehash is triggered.

Delete

O(n)

O(1)

Worst case with many collisions.

Set Implementation Using HashMap

JavaScript’s built‑in Set can be replaced with a custom implementation that uses the above HashMap to guarantee uniqueness.

class MySet {
  constructor() { this.map = new HashMap(); }
  add(value) { this.map.set(value); }
  has(value) { return !!this.map.get(value); }
  get size() { return this.map.size; }
  delete(value) { return this.map.delete(value); }
  entries() {
    return this.map.keys.reduce((acc, key) => {
      if (key) acc.push(key.content);
      return acc;
    }, []);
  }
}

The average time for add, has, and delete is O(1) , while entries is O(n) .

Singly Linked List

class Node { constructor(value) { this.value = value; this.next = null; } }
class LinkedList {
  constructor() { this.root = null; }
  addLast(value) { /* O(n) if list not empty */ }
  removeLast() { /* O(n) */ }
  addFirst(value) { const node = new Node(value); node.next = this.root; this.root = node; }
  removeFirst() { if (!this.root) return null; const val = this.root.value; this.root = this.root.next; return val; }
  remove(index=0) { /* O(n) */ }
  contains(value) { /* O(n) */ }
}

Operations at the head are O(1) ; operations at the tail or arbitrary positions are O(n) .

Doubly Linked List

class DNode { constructor(value) { this.value = value; this.next = null; this.prev = null; } }
class DoublyLinkedList {
  constructor() { this.first = null; this.last = null; this.size = 0; }
  addFirst(value) { const node = new DNode(value); if (this.first) { this.first.prev = node; node.next = this.first; } else { this.last = node; } this.first = node; this.size++; }
  addLast(value) { const node = new DNode(value); if (this.last) { node.prev = this.last; this.last.next = node; this.last = node; } else { this.first = node; this.last = node; } this.size++; }
  removeFirst() { if (!this.first) return null; const val = this.first.value; this.first = this.first.next; if (this.first) this.first.prev = null; else this.last = null; this.size--; return val; }
  removeLast() { if (!this.last) return null; const val = this.last.value; this.last = this.last.prev; if (this.last) this.last.next = null; else this.first = null; this.size--; return val; }
  add(value, index) { /* O(n) for middle insertion */ }
  remove(index) { /* O(n) */ }
  contains(value) { /* O(n) */ }
}

Both head and tail insertions/deletions are O(1) ; middle operations remain O(n) .

Stack (LIFO) Using Array

class Stack {
  constructor() { this.store = []; }
  push(el) { this.store.push(el); return this; }
  pop() { return this.store.pop(); }
}

Both push and pop run in O(1) .

Queue (FIFO) Implementations

Simple array‑based queue:

class Queue {
  constructor() { this.store = []; }
  add(el) { this.store.push(el); }
  remove() { return this.store.shift(); } // O(n)
}

Improved two‑stack queue (amortized O(1)):

class Queue {
  constructor() { this.in = []; this.out = []; }
  add(el) { this.in.push(el); }
  remove() {
    if (!this.out.length) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    return this.out.pop();
  }
}

Using a doubly linked list gives true O(1) enqueue and dequeue:

class Queue {
  constructor() { this.list = new DoublyLinkedList(); }
  add(el) { this.list.addFirst(el); }
  remove() { return this.list.removeLast(); }
  get size() { return this.list.size; }
}

Summary of Time Complexities

Data Structure

Insert

Access

Search

Delete

Notes

Array

O(n)

O(1)

O(n)

O(n)

Appending at the end is O(1).

(Hash) Map

O(1)*

O(1)*

O(1)*

O(1)*

Re‑hashing may affect insertion.

Map (BST)

O(log n)

-

O(log n)

O(log n)

Implemented with a binary search tree.

Set (HashMap)

O(1)*

-

O(1)*

O(1)*

Implemented via HashMap.

Set (List)

O(n)

-

O(n)

O(n)

Implemented with a List.

Set (BST)

O(log n)

-

O(log n)

O(log n)

Implemented with a BST.

Linked List (singly)

O(n)

-

O(n)

O(n)

Head insertion/deletion is O(1).

Linked List (doubly)

O(n)

-

O(n)

O(n)

Head/Tail insertion/deletion is O(1); middle positions O(n).

Stack (Array)

O(1)

-

-

O(1)

LIFO behavior.

Queue (simple Array)

O(n)

-

-

O(1)

Dequeue uses Array.shift (O(n)).

Queue (improved Array)

O(1)*

-

-

O(1)

Amortized O(1) enqueue; occasional O(n) re‑balancing.

Queue (List)

O(1)

-

-

O(1)

Implemented with a doubly linked list.

Binary search trees, other tree structures, and graphs will be covered in a separate article.

Original source: www.zcfy.cc/article/data-structures-for-beginners-arrays-hashmaps-and-lists

Java Leader

Focus on Java practical sharing

Scan the QR code above for more Java content