VJC Chapter 14 Linked Lists

VJC/H2Computing/9569 Chapter 14 Linked Lists Contents 1 Abstract Data Type (ADT) 2 Linked Lists 3 Operations of Singly Linked Lists using OOP 3.1 Creating a new linked list 3.2 Inserting a node 3.3 Deleting a node 3.4 Search for data 3.5 Access all nodes stored in the Linked List 4 Linked list using arrays 4.1 Inserting a node 4.2 Deleting a node 5 Free space list Syllabus Learning Outcomes 1.3 Data Structures Understand concept and write algorithms for stack, queue (linear and circular), linear linked list and binary search tree. 1.3.1 Understand the concept of static allocation of memory. 1.3.2 Understand the concept of dynamic allocation of memory. 1.3.4 Understand the concept of free space list (which could be another linked list or an array). 1.3.5 Create, update (edit, insert, delete) and search operations for a linear linked list. Exclude: doubly-linked list and circular linked list 2.3 Implementing Algorithms and Data Structures Use programming language elements and constructs to implement sort and search algorithms such as insertion sort, bubble sort, quicksort, merge sort, linear search, binary search and hash table search, as well as data structures such as stacks, queues, linear linked lists and binary search trees. 2.3.3 Write programs to implement operations for stacks, queues (linear and circular), linear linked lists and binary search trees. Exclude: doubly-linked list and circular linked list 1

VJC/H2Computing/9569 1 Abstract Data Type (ADT) An Abstract Data Type (ADT) is a collection of data and a set of associated operations: - create a new instance of the data structure - insert a new element into the data structure - delete an element from the data structure - find/update an element in the data structure - access all elements stored in the data structure in a systematic manner. One can use an ADT’s operations without knowing how the operations are implemented or how the data is stored. Examples of ADTs: Linked lists, stacks, queues and binary trees. 2 Linked Lists An array is defined as a collection of items that are stored at contiguous (adjacent) memory locations. It is a container which can hold a fixed number of items , and these items should be of the same type . A linked list is a dynamic data structure , which holds a collection of elements. The individual element may not be stored in contiguous memory locations but at whatever location that is available, and the elements are linked int