08 Common Containers

January 10, 2024 · 2 min read

If you have any questions, feel free to comment below. Click the block can copy the code.
And if you think it's helpful to you, just click on the ads which can support this site. Thanks!

8.1 List #

Interface: java.util.List<>.

Implementations:

• java.util.ArrayList<>: resizable array
• java.util.LinkedList<>: doubly linked list

Methods:

• add(): add an element at the end
• clear(): clear the list
• size(): return its length
• isEmpty(): check whether it is empty
• get(i): get the ith element
• set(i, val): set the ith element to val

Loop syntax:

// Standard
for(int i = 0; i < list.size(); i ++) {  
    System.out.println(list.get(i));  
}
// Enhanced
for (Integer integer : list) {  
    System.out.println(integer);  
}

8.2 Stack #

Note that, among these implementations, only the stack is a class rather than an interface.

Class: java.util.Stack<>

Methods:

• push(): push an element
• pop(): remove and return the top element
• peek(): return the top element
• size(): return its length
• empty(): check whether the stack is empty
• clear(): clear the stack

import java.util.Stack;  
  
public class Main {  
    public static void main(String[] args) {  
        Stack<Integer> stk = new Stack<>();  
        stk.push(1);  
        stk.push(2);  
        System.out.println(stk.pop());  
        System.out.println(stk.peek());  
    }  
}

8.3 Queue #

Interface: java.util.Queue<>

Implementations: Note: there is no ArrayList implementation.

• java.util.LinkedList<>: doubly linked list
• java.util.PriorityQueue<>: priority queue
  • A min-heap by default; for a max-heap, use new PriorityQueue<>(Collections.reverseOrder())

Methods:

• add(): add an element at the rear of the queue
• remove(): remove and return the front element
• isEmpty(): check whether it is empty
• size(): return its length
• peek(): return the front element
• clear(): clear the queue

public class Main {  
    public static void main(String[] args) {  
        Queue<Integer> q = new LinkedList<>();  
        q.add(1);  
        q.add(2);  
        System.out.println(q.remove());  
        System.out.println(q.peek());  
    }  
}

8.4 Set #

Interface: java.util.Set<K>

Implementations:

• java.util.HashSet<K>: hash table (not necessarily ordered)
• java.util.TreeSet<K>: balanced tree (always ordered; implemented with a red-black tree)

Methods:

• add(): add an element
• contains(): check whether it contains an element
• remove(): remove an element
• size(): return the number of elements
• isEmpty(): check whether it is empty
• clear(): clear the set

Additional methods of java.util.TreeSet:

• ceiling(key): return the smallest element greater than or equal to key, or null if none exists
• floor(key): return the largest element less than or equal to key, or null if none exists

public class Main {  
    public static void main(String[] args) {  
        Set<Integer> set = new HashSet<>();  
        set.add(161);  
        set.add(222);  
        set.add(160);  
  
        for(int x : set) {  
            System.out.println(x);  
        }  
    }  
}

8.5 Map #

Interface: java.util.Map<K, V>

Implementations:

• java.util.HashMap<K, V>: hash table (not necessarily ordered)
• java.util.TreeMap<K, V>: balanced tree (always ordered; implemented with a red-black tree)

Methods:

• put(key, value): add a key and its corresponding value
• get(key): return the value corresponding to a key
• containsKey(key): check whether it contains a key
• remove(key): remove a key
• size(): return the number of elements
• isEmpty(): check whether it is empty
• clear(): clear the map
• entrySet(): get the set of all entries in the Map
• Map.Entry<K, V>: the type of an entry in the Map
  • getKey(): get the key
  • getValue(): get the value

public class Main {  
    public static void main(String[] args) {  
        Map<String, Integer> map = new HashMap<>();  
        map.put("123", 1);  
        map.put("345", 2);  
        map.put("678", 6);  
  
        System.out.println(map.containsKey("123"));  
        for(Map.Entry<String, Integer> entry : map.entrySet())  
            System.out.printf("%s %d\n", entry.getKey(), entry.getValue());  
    }  
}

Additional methods of java.util.TreeMap<K, V>:

• ceilingEntry(key): return the smallest entry with a key greater than or equal to key, or null if none exists
• floorEntry(key): return the largest entry with a key less than or equal to key, or null if none exists

public class Main {  
    public static void main(String[] args) {  
        TreeMap<Integer, Integer> map = new TreeMap<>();  
        map.put(123, 1);  
        map.put(345, 2);  
        map.put(678, 6);  
  
        Map.Entry<Integer, Integer> down = map.floorEntry(124);  
        System.out.println(down);  
    }  
}

Correspondences with C++:

List -----> list
Queue ----> queue
PriorityQueue ---> priority_queue
Stack ----> stack
TreeSet ----> set
HashSet ----> unordered_set
TreeMap ----> map
HashMap ----> unordered_map

Related readings

• 07 Classes and Interfaces
• 06 Functions
• 05 Strings
• 04 Arrays
• 03 Loops