List ADT | Linked Lists | Trees, Tries & Graphs | Stacks & Queues Heaps | Hash Tables
Algorithms: Breadth-First Search | Depth-First Search | Binary Search | Merge Sort | Quick Sort
Concepts: Memory (Stack vs. Heap) | Recursion | Big O Time & Space
Why even learn Data Structures & Algorithms?
- Quite simply because Algorithms + Data Structures = Programs (Niklau)
- Any program is going to need some type of data structure to store and manage the data that it is manipulating and one or more algorithms for translating that data from its input form to its output form.
- There is always more than one data structure or algorithm for a particular problem so studying the pros and cons of each type is a critical skill for a programmer.
So, first up…
1. List ADT (Abstract Data Type)
- Lists are the most ubiquitous organizing tool that we all have.
- Computers also use lists to organize and store data.
- Lists are good especially if we have small number of items to store and don’t need the data to be sorted. Or if we don’t need to perform long searches on them.
- A list is simply an ordered sequence of data.
- Each data item stored is called an element and can be of any data type.
- You can append an element to the end of a list, or you can insert an element after an existing element or at the beginning of a list. You can remove elements by using a remove operation.
- A list has a front and an end. The next operation moves you to the next element while the prev operation moves you one back. The currPos property indicates the current position in a list.
- Below is the List class implementation
- Methods of the List class
- Creating a List class instance and traversing through it
Next up: Linked Lists!