Java Data Structures

Java provides a rich set of data structures to handle and organize data.

Java's java.util package provides implementations of many of these data structures, and you can choose the appropriate class as needed.

The following are some common Java data structures:

Arrays

Arrays are a basic data structure that can store a fixed-size collection of elements of the same type.

int[] array = new int[5];
  • Characteristics:Fixed size, stores elements of the same type.
  • Advantages:Efficient random access to elements.
  • Disadvantages:Fixed size, insertion and deletion of elements are relatively slow.

Lists

Java provides multiple list implementations, such as ArrayList and LinkedList.

List<String> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

ArrayList:

  • Characteristics:Dynamic array, variable size.
  • Advantages:Efficient random access and fast tail insertion.
  • Disadvantages:Insertion and deletion in the middle are relatively slow.

LinkedList:

  • Characteristics:Doubly linked list, elements are connected by pointers.
  • Advantages:Efficient insertion and deletion of elements, good iterator performance.
  • Disadvantages:Random access is relatively slow.

Sets

Sets are used to store non-duplicate elements, and common implementations include HashSet and TreeSet.

Set<String> hashSet = new HashSet<>();
Set<Integer> treeSet = new TreeSet<>();

HashSet:

  • Characteristics:Unordered collection, implemented based on HashMap.
  • Advantages:Efficient search and insertion operations.
  • Disadvantages:Does not guarantee order.

TreeSet:

  • Characteristics:TreeSet is an ordered collection, implemented based on a red-black tree at the bottom layer, and does not allow duplicate elements.
  • Advantages:Provides automatic sorting functionality, suitable for scenarios where elements need to be stored in order.
  • Disadvantages:Performance is relatively poor, and null elements are not allowed to be inserted.

Maps

Maps are used to store key-value pairs, and common implementations include HashMap and TreeMap.

Map<String, Integer> hashMap = new HashMap<>();
Map<String, Integer> treeMap = new TreeMap<>();

HashMap:

  • Characteristics:A key-value pair storage structure implemented based on a hash table.
  • Advantages:Efficient search, insertion, and deletion operations.
  • Disadvantages:Unordered, does not guarantee order.

TreeMap:

  • Characteristics:An ordered key-value pair storage structure implemented based on a red-black tree.
  • Advantages:Ordered, supports traversal in the order of keys.
  • Disadvantages:Insertion and deletion are relatively slow.

Stack

A stack is a linear data structure that manages elements according to the Last In, First Out (LIFO) principle. In a stack, new elements are added to the top of the stack, and elements can only be removed from the top of the stack. This means that the last element added is the first one to be removed.

Stack<Integer> stack = new Stack<>();

Stack class:

  • Characteristics:Represents a stack, usually operating on elements in a Last In, First Out (LIFO) order.

Queue

Queues follow the First In, First Out (FIFO) principle, and common implementations include LinkedList and PriorityQueue.

Queue<String> queue = new LinkedList<>();

Queue interface:

  • Characteristics:Represents a queue, usually operating on elements in a First In, First Out (FIFO) order.
  • Implementation classes: LinkedList, PriorityQueue, ArrayDeque。

Heap

A heap is the foundation of a priority queue, and can implement max-heap and min-heap.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Trees

Java provides the TreeNode type, which can be used to build data structures such as binary trees.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Graphs

Representing graphs usually requires custom data structures or using graph libraries; Java has no built-in graph class.

The above are only some common data structures in Java. In fact, there are many other data structures and algorithms that can be selected and used according to specific problems.

Other Notes

The following classes are traditionally legacy. In Java 2, a new framework, the Collection Framework, was introduced, which we will discuss later.

Enumeration

The Enumeration interface, although it is not itself a data structure, is widely used in the scope of other data structures. The Enumeration interface defines a way to retrieve consecutive elements from a data structure.

For example, Enumeration defines a method called nextElement, which is used to get the next element of a data structure containing multiple elements.

For more information about the Enumeration interface,please see Enumeration。

BitSet

The BitSet class implements a group of bits or flags that can be individually set and cleared.

This class is very useful when dealing with a group of boolean values. You only need to assign one "bit" to each value, and then set or clear the bits appropriately to operate on the boolean values.

For more information about this class,please see BitSet。

Vector

The Vector class is very similar to a traditional array, but the size of Vector can change dynamically as needed.

Like arrays, elements of Vector objects can also be accessed by index.

The main benefit of using the Vector class is that you do not need to specify a size for the object when creating it; its size changes dynamically as needed.

For more information about this class,please see Vector

Stack

The Stack implements a Last In, First Out (LIFO) data structure.

You can understand a stack as a vertically distributed stack of objects. When you add a new element, you place it on top of the other elements.

When you take an element from the stack, you take it from the top of the stack. In other words, the element that entered the stack last is removed first.

For more information about this class,please see Stack。

Dictionary

The Dictionary class is an abstract class that defines a data structure that maps keys to values.

When you want to access data through a specific key rather than an integer index, you should use Dictionary.

Since the Dictionary class is an abstract class, it only provides a data structure for mapping keys to values, but does not provide a specific implementation.

For more information about this class,please see Dictionary。

The Dictionary class has been deprecated in newer Java versions. It is recommended to use the Map interface and its implementation classes, such as HashMap, TreeMap, etc., to replace Dictionary.

For the Map interface and its implementation classes, please refer to:Java Collections Framework。

Hashtable

The Hashtable class provides a means of organizing data based on a user-defined key structure.

For example, in a hashtable of an address list, you can store and sort data based on postal code as the key, rather than by person's name.

The specific meaning of a hashtable key depends entirely on the usage scenario of the hashtable and the data it contains.

For more information about this class,please see Hashtable。

Properties

Properties inherits from Hashtable. The Properties class represents a persistent set of properties. Each key and its corresponding value in the property list is a string.

The Properties class is used by many Java classes. For example, it serves as the return value of the System.getProperties() method when obtaining environment variables.

For more information about this class,see Properties。

Other extensions