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 into an ordered sequence using pointers. An element in the list is called a node . A node contains both data and a “link” to the next element. The “link” is usually referred to as a pointer , which is a variable that stores the address of the next node it points to. A pointer that does not point at anything, indicating no further elements, is called a null pointer . It is usually represented by Ø. In program code, we set it to None . The start/head pointer stores the address of the first element (a link that points to the first node). There are different types of linked list: singly linked list, doubly linked list and circular linked list. A singly linked list is a collection of nodes, each containing one pointer pointing to the next node. The start pointer points to the first node, and the pointer in the last node points to null. When the list is empty, the start pointer points to null. With only one pointer, it can only traverse forward along the list. A doubly linked list is a collection of nodes, each containing two pointers, one pointing to the previous node and the other pointing to the next node respectively. With two pointers, we can traverse forward and backward along the list. (Not in syllabus) A circular linked list is similar to a singly linked list, but with the pointer in the last node pointing back to the first node. (Not in syllabus) For the remaining of this chapter, we will focus on singly linked list. 2

VJC/H2Computing/9569 3 Operations of Singly Linked Lists using OOP 3.1 Creating a new linked list In the examples which follow, we will assume each node consists of a data and a next pointer, pointing to the next node in the list. A class Node contains two attributes: data and a next pointer. A class LinkedList contains one attribute: start . The constructor will initialise an empty linked list and set the start pointer to null. 3

VJC/H2Computing/9569 3.2 Inserting a node A linked list can be either an ordered or unordered linked list. For an unordered linked list, a new node can be inserted either at the beginning of the list or at the end of the list. To insert a new node, C, at the beginning of the list: Step 1: the pointer in the new node, C, has to point to the content of the Start pointer Step 2: the Start pointer is then set to point to the new node, C. To insert the new note, C, at the end of the list: Step 1: the pointer of node L (the last node) points to the new node, C. The pointer of the new node, C, contains the null pointer. To insert a new node into an ordered linked list, the new node may need to be inserted between two existing nodes. To insert a new node, C, between existing nodes, B and D: Step 1: the pointer of node C has to point to the content of the pointer in B Step 2: the pointer in B is then set to point to the new node, C. 4

VJC/H2Computing/9569 The algorithm for inserting a node into an ordered linked list: PROCEDURE insert(self, data) //Create a node object new_node Node(data) IF self.start IS NONE //Linked list is empty THEN self.start new_node //insert new_node as first node ELSE //Find insertion point current self.start //start at beginning of list previous current WHILE current IS NOT NONE AND current.data < data previous current //remember current node current current.next //follow the pointer to the next node ENDWHILE IF previous == current //insert new_node at the start of list THEN new_node.next current self.start new_node ELSE IF current IS NONE //insert new_node at the end of list THEN previous.next new_node ELSE //insert new_node between previous and current new_node.next current previous.next new_node ENDIF ENDIF ENDIF ENDPROCEDURE 3.3 Deleting a node To delete the first node in the list, the Start pointer is set to point to the content of the pointer of the first node. 5

VJC/H2Computing/9569 6

VJC/H2Computing/9569 To delete the last node i