Data Structures & Algorithms Notes Page

Abstract Data Type

• An Abstract Data Type (ADT) is a model of data structure that specifies:

  • Characteristics of the collection of data
  • Operations that can be performed on the collection

• In JAVA, ADT can be specified using an interface.

List Abstract Data Type

• A list is a sequence of elements

  • May contain duplicates or null
  • Elements have a specific position (index)
  • Dynamic Size:
    • Lists can grow or shrink as needed (unlike arrays, which have a fixed size)
  • List is a type of interface in Java

• Notation:

  • $<A_0, A_1, ..., A_{n-1}>$
  • Example: $<5, 7, 8, 1, 25>$

• Element in a list has a position

List ADT → Operations and Implementations

Basic Operations:

• insert/add(x): Add new element x at the end of the list