Lecture Algorithms and data structures: Chapter 16 - Singly Linked List. The main contents of the chapter consist of the following: Accessing the root, given an object in the container: Access the parent of the current object, find the degree of the current object, get a reference to a child, attach a new sub-tree to the current object, detach this tree from its parent. | Review Deleting an Element from a Linked List Deletion involves: Getting to the correct position Moving a pointer so nothing points to the element to be deleted Can delete from any location Front First occurrence All occurrences Singly link list All the nodes in a singly linked list are arranged sequentially by linking with a pointer. A singly linked list can grow or shrink, because it is a dynamic data structure. figure explains the different operations on a singly linked list. Insertion and Deletion Singly Link list Learn about linked lists Become aware of the basic properties of linked lists Explore the insertion and deletion operations on linked lists Discover how to build and manipulate a linked list Introduction Data can be organized and processed sequentially using an array, called a sequential list Problems with an array Array size is fixed Unsorted array: searching for an item is slow Sorted array: insertion and deletion is slow Linked Lists Linked list: a list of items (nodes), in which the order of the nodes is determined by the address, called the link, stored in each node Link field in last node is NULL Linked Lists (cont'd.) Because each node of a linked list has two components, we need to declare each node as a class or struct Data type of a node depends on the specific application The link component of each node is a pointer Linked Lists: Some Properties Linked Lists: Some Properties (cont'd.) current = head; Copies value of head into current Linked Lists: Some Properties (cont'd.) current = current->link; Traversing a Linked List The basic operations of a linked list are: Search to determine if an item is in the list Insert an item in the list Delete an item from the list Traversal: given a pointer to the first node of the list, step through the nodes of the list Traversing a Linked List (cont'd.) To traverse a linked list: Example: Item Insertion and Deletion Consider the following definition | Review Deleting an Element from a Linked List Deletion involves: Getting to the correct position Moving a pointer so nothing points to the element to be deleted Can delete from any location Front First occurrence All occurrences Singly link list All the nodes in a singly linked list are arranged sequentially by linking with a pointer. A singly linked list can grow or shrink, because it is a dynamic data structure. figure explains the different operations on a singly linked list. Insertion and Deletion Singly Link list Learn about linked lists Become aware of the basic properties of linked lists Explore the insertion and deletion operations on linked lists Discover how to build and manipulate a linked list Introduction Data can be organized and processed sequentially using an array, called a sequential list Problems with an array Array size is fixed Unsorted array: searching for an item is slow Sorted array: insertion and deletion is slow Linked Lists Linked
