TAILIEUCHUNG - Lecture Algorithms and data structures (CSC112) - Chapter 16

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

• Kỹ thuật lập trình
• Data structures
• Lecture Algorithms and data structures
• Thiết kế thuật toán
• Cấu trúc dữ liệu
• Algorithm analysis
• Graph algorithms
• Design techniques
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Memory allocation
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming