Basic data structures in different languages

Having dealt with multiple different programming languages creates some confusion how and in which place the data structures are implemented in each of the languages. This page tries to provide some overview of basic data structures.

• Threading
• Lock
• RLock
• Condition
• Semaphore
• Event
• Queue

http://www.laurentluce.com/posts/python-threads-synchronization-locks-rlocks-semaphores-conditions-events-and-queues/

LIFO

Stack<E>

or

Deque<Integer> stack = new ArrayDeque<Integer>();

Operations:

empty, pop, peek, push, search

// simple lists
letters = []
last_item = letters.pop()

Operations:

append, pop

FIFO

Collection interface Queue

1. Thread-safe: PriorityBlockingQueue
2. Not Thread-safe: PriorityQueue, LinkedList

Operations

add()
peek()
element() throws NoSuchElementException when queue is empty
remove() removes and returns the head of the queue
poll()
size()

from collections import deque
first_item = numbers.popleft()

Operations:

append, pop, popleft

• Multiproducer, multiconsumer queues
• Queue, SimpleQueue (no task tracking), LifoQueue, PriorityQueue

For uncomparable types:

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

For multi-processing

Heap structure (binary tree with ordering); Priority queue

Use cases:

Minheap implementation

import heapq

heapq.heappush, heapq.heapppop
heapq.heapify - Transform list to heap

Maintain list in sorted ordered on insertion.

array module - “typed” lists

Math.min, Math.max
(int) Math.pow(2, 3)

str.indexOf // (first occurence of Character/String;  + index to start; Returns -1 if not found, else idx
str.charAt // Character
str.substring(int beginIndex, int endIndex) // actual start (=0), but end is lenght)