Data structure

A data structure is a way to store and organise data. Our choice of what data structure to use is important — because it may change the runtime complexity of basic operations, like searching, inserting, and deleting nodes.

We implement data structures in classes in most languages. In some languages, like C/C++, we may use the struct type to implement data structures.

Basic operations

Often we are interested in the implementation and space/time complexity of a few basic operations:

• Searching through the structure for a certain value
• Inserting data, perhaps depending on a sorting condition
• Deleting a node with particular data or the structure
• Copying the structure from one to another

While writing functions for these operations, consider:

• Will they work if the structure is empty?
• Will they work if the data is not in the list?
• Will they work if we need to work regardless of the position?
  • If at the end, set next pointer to null.
  • If at the head, change the head pointer.
  • If in the middle, ensure pointers behind and in front are properly updated.

Common data structures

• Array
  • Vector (C++)
• Linked list
• Trees
  • Binary tree
    • Binary search tree
      • AVL tree
      • Red-black tree
  • B-tree
  • Prefix tree

Courses

• APS105 — Computer Fundamentals
• ECE244 — Programming Fundamentals
• ECE297 — Software Design and Communication
• ECE345 — Algorithms and Data Structures

Resources

• Introduction to Algorithms, by Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein (CLRS)
• Data Structures and Algorithms in {Java, C++, Python}, by Michael Goodrich and Roberto Tamassia

See also

• Algorithm
• Abstract data type
• Database