Data Structures — Language Support (Part 3)

A quick glance on language support for different data structures.

Arrays

Support for N-th dimensional arrays is generally built directly into the core language itself. They exist in most of languages if not all of them.

Some languages index from zero while others index from one.

Dynamic Arrays

Java

Java offers a couple of classes, the best known being the ArrayListclass.

Python

In Python, listis a data type, just like strings and numbers. It’s an implementation of dynamic arrays.

C++

C++’s std::vector is an implementation of dynamic arrays.

C#

C# also offers ArrayListclass as in Java.

Linked List

Java

In Java, Listis an interface, where LinkedListclass implements the Listinterface. It’s implemented as doubly-linked list.

Python

Python does not have a built-in linked list implementation. Python lists are not linked lists, they are dynamic arrays.

C++

The listcontainer in the standard temple library is a doubly-linked list implementation.

C#

In C#, there is a LinkedListclass as in Java. It’s also implemented as doubly-linked list.

Stacks

Java

In Java, it has a Stack class.

Python

Python doesn’t have an explicit stack class, but there is a section in the Python documentation of using lists as stacks.

C++

In C++, stack is part of the standard template library.

C#

C# also offers Stack class as in Java.

Queues

Java

Queueis an interface just as List was. There are multiple concrete classes that do support queue behavior. The LinkedListclass actually supports a simple queue behavior.

Python

The queuemodule offers a queue class. It is especially useful in when working with threading which is very common with queues. It’s also possible to use list as queues, however, lists are not efficient for this purpose.

collections.deque is an alternative implementation of unbounded queues with fast atomic append() and popleft() operations that do not require locking.

C++

In C++, there is a queuecontainer in the standard template library.

C#

In C#, there is a Queueclass.

Deque

Java

Java also has aDequeinterface just as Queue was. The LinkedListclass also implements that Dequeinterface.

Notice that LinkedList is turning out to be a very flexible class in Java. It can behave like a linked list and it can behave like a queue, and it can behave like a double ended queue; deque.

Python

Python also has a dequeclass for this. Even though you could use a Python list, the deque is optimized for this kind of usage; appends and pops on either end.

C++

In C++, there is a dequecontainer.

C#

It doesn’t have a built in explicit deque, but, we can provide equivalent behavior with a linked list or even a dynamic array. Just be conscious as shifting elements around in the array is not an efficient task.

Priority Queues

Just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.

Java

Java has a PriorityQueueclass, which is based on a priority heap.

Python

The queuemodule offers a PriorityQueueclass, which uses heapq module under the hood to prioritize the queue entries. The heapq module uses the heap data structure.

Queue.PriorityQueue is a thread-safe class, while the heapq module makes no thread-safety guarantees.

C++

C++ has priority_queuecontainer, which is also implemented as a heap data structure.

C#

C# doesn’t contain a priority queue class. But, there are several implementations for priority queues available on the internet.

Associative Arrays

Most associate arrays, whether they are called dictionaries or maps or hash, are implemented using something called a hash table, and a hash table itself is a very important and useful data structure.

Other languages use binary search tree (probably a red black tree; a type of self balancing binary search tree) where each node has a key and associated value. So, if you want to keep your keys in a sorted order, hash tables aren’t really good at that, but, binary search trees are.

Java

In Java, It has Map interface just as List was. It defines the operations for associative arrays, while HashMap and HashTable classes are implementations of these operations based on the hash table data structure.

HashTable is better when working with multi-threaded applications, where you have different threads accessing and changing this hash table, but it will add a performance cost.

ConcurrentHashMapclass is a replacement for the older HashTable.

There is also LinkedHashMap, which use linked list to iterate over the items in the same way they were inserted.

While TreeMap class also implements the Map interface, it’s actually a RedBlackTree, which is a self-balancing binary search tree.

Python

In Python, they are called dictionaries. They are implemented as a data type called dict, just like strings and numbers.

C++

C++ offers std::unordered_mapcontainer in the standard template library, while std::mapcontainer is the sorted version which is typically implemented as binary search tree.

C#

In C#, they’re available in Dictionary<TKey,TValue>, Hashtableand StringDictionaryclasses, whileSortedDictionaryclass sorts the key-value pairs that’s implemented as a binary search tree.

Sets

The idea of a set; having a big container where you can put a bunch of items into it, is usually implemented using hash tables, or binary search trees.

Java

In Java, It has Set interface just as List and Queue, whileHashSet and TreeSetclasses implement the Setinterface.

HashSet is internally implemented using an HashMap, while TreeSet is internally implemented using TreeMap.

Python

Python supports set and frozensetdata types. frozenset is a way of making the set immutable after it has been created.

C++

As with maps, C++ also offers std::unordered_setcontainer in the standard template library, while std::setcontainer is the sorted version which is typically implemented as binary search tree.

C#

C# also offers HashSet class which uses the hash table as in Java, while SortedSet is the sorted version.

Graphs

There is no direct support for graph data structure in languages(same as trees). Because the implementation of any graph is always going to be more specific.

For example, A linked list is a kind of graph, a tree is a kind of graph, a heap is a kind of graph. A single linked list would be considered a directed graph, whereas a doubly linked list is a kind of undirected graph. They are all graphs with intentional constraints.

Summary for Data Structures Language Support