Pre-Defined ADTs - Lists, Queues, Stacks and Dictionaries

Pre-Defined ADTs - Lists, Queues, Stacks and Dictionaries

Understanding Pre-Defined Abstract Data Types (ADTs)

  • Abstract Data Types (ADTs) are a means of classifying data structures based on their behaviour.
  • Commonly used pre-defined ADTs include lists, queues, stacks, and dictionaries.
  • Understanding these ADTs can greatly help with the efficient implementation and organisation of data in software applications.

Lists

  • Lists are a fundamental ADT that store an ordered collection of items, which can include integers, strings, or other ADTs.
  • Lists allow flexible size changes, inclusion and removal of elements, and are capable of storing different types of data.
  • Indexing is used in lists to access elements by referring to their position within the list.
  • Lists can also be nested, meaning a list can contain other lists as its elements.
  • Key list operations include append(item), insert(index, item), remove(item), and index(item).

Queues

  • A queue is an ADT where the entity first added to the collection will be the first one to be removed - this principle is sometimes referred to as First-In, First-Out (FIFO).
  • Queues are often used when tasks are lined up for execution, such as printing documents or managing processes in an operating system.
  • Key queue operations include enqueue(item), which adds an item to the rear of the queue, and dequeue(), which removes an item from the front of the queue.

Stacks

  • A stack is an ADT in which the last entity added to the stack is the first one to be removed - this principle is known as Last-In, First-Out (LIFO).
  • Stacks are widely used in programming languages for things like function call management, backtracking problems and more.
  • Key stack operations include push(item), which adds an item to the top of the stack, and pop(), which removes the topmost item of the stack.

Dictionaries

  • A dictionary (also known as a map or hash map in some languages) is an ADT where data is stored in key-value pairs.
  • Unlike lists, dictionaries aren’t ordered and use keys (unique within the dictionary) to access values.
  • This allows for a very efficient retrieval of data associated with a particular key.
  • Key dictionary operations include getItem(key), setItem(key, value), delItem(key), and getKeys().

Choosing the Right ADT

  • The choice of pre-defined ADT to use in a solution should depend on the specific requirements of the problem and the operations that need to be performed on the data.
  • For example, if a solution requires the frequent addition and removal of entities in an order-dependent manner, using a queue might be more suitable than using a list.
  • Dictionaries would be suitable in cases which require associating values with unique keys for efficient data access.
  • Understanding the benefits and limitations of each of these ADTs can lead to more efficient and effective solutions.