Data Structures and Algorithms: Arrays and Linked Lists includes Arrays (Built-in in most programming languages, Two kinds); Singly Linked Lists, Abstract Data Types (ADTs), Position ADT. | Arrays and Linked Lists Data Structures and Algorithms Acknowledgement: These slides are adapted from slides provided with Data Structures and Algorithms in C++ Goodrich, Tamassia and Mount (Wiley, 2004) Outline Arrays Singly Linked Lists Doubly Linked Lists Linked Lists 2 Arrays Built-in in most programming languages Two kinds (programmer responsibility): Unordered: attendance tracking Ordered: high scorers Operations: Insertion Deletion Search Linked Lists 3 Arrays Operation Unordered Ordered Insertion O(1) O(n) Deletion O(n) O(n) Search O(n) O(logn) Pluses & minuses + Fast element access; simple -- Impossible to resize; slow deletion • Many applications require resizing! • Required size not always immediately available. Linked Lists 4 Abstract Data Types (ADTs) An abstract data type (ADT) is an abstraction of a data structure An ADT specifies: Data stored Operations on the data Error conditions associated with operations Linked .
