Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Algorithms and data structures: Chapter 17 - Singly Linked List

This topic will cover tree traversals: A means of visiting all the objects in a tree data structure, we will look at breadth-first traversals and depth-first traversals (Pre-order and Post-order depth-first traversals), applications, general guidelines. | Linked List as an ADT The basic operations on linked lists are: Initialize the list Determine whether the list is empty Print the list Find the length of the list Destroy the list Linked List as an ADT (cont'd.) Retrieve the info contained in the first node Retrieve the info contained in the last node Search the list for a given item Insert an item in the list Delete an item from the list Make a copy of the linked list Linked List as an ADT (cont'd.) In general, there are two types of linked lists: Sorted and unsorted lists The algorithms to implement the operations search, insert, and remove slightly differ for sorted and unsorted lists The abstract class linkedListType will implement the basic linked list operations Derived classes: unorderedLinkedList and orderedLinkedList Linked List as an ADT (cont'd.) If a linked list is unordered, we can insert a new item at either the end or the beginning buildListForward inserts item at the end buildListBackward inserts new item at the beginning To accommodate both operations, we will write two functions: insertFirst and insertLast We will use two pointers in the list: first and last Structure of Linked List Nodes The node has two member variables To simplify operations such as insert and delete, we define the class to implement the node of a linked list as a struct The definition of the struct nodeType is: Member Variables of the class linkedListType We use two pointers: first and last We also keep a count of the number of nodes in the list linkedListType has three member variables: Linked List Iterators One of the basic operations performed on a list is to process each node of the list List must be traversed, starting at first node Common technique is to provide an iterator Iterator: object that produces each element of a container, one element at a time The two most common operations are: ++ (the increment operator) * (the dereferencing operator) Linked List Iterators (cont'd.) Note that an . | Linked List as an ADT The basic operations on linked lists are: Initialize the list Determine whether the list is empty Print the list Find the length of the list Destroy the list Linked List as an ADT (cont'd.) Retrieve the info contained in the first node Retrieve the info contained in the last node Search the list for a given item Insert an item in the list Delete an item from the list Make a copy of the linked list Linked List as an ADT (cont'd.) In general, there are two types of linked lists: Sorted and unsorted lists The algorithms to implement the operations search, insert, and remove slightly differ for sorted and unsorted lists The abstract class linkedListType will implement the basic linked list operations Derived classes: unorderedLinkedList and orderedLinkedList Linked List as an ADT (cont'd.) If a linked list is unordered, we can insert a new item at either the end or the beginning buildListForward inserts item at the end buildListBackward inserts new item .