Đang chuẩn bị liên kết để tải về tài liệu:
Ebook Data Structures and Algorithms Using C#: Part 2

Part 2 consists of 7 chapters introduce content: Linked Lists, Binary Trees and Binary Search Trees, Sets, Advanced Sorting Algorithms, Advanced Data Structures and Algorithms for Searching, Graphs and Graph Algorithms, Advanced Algorithms. | Chapter 11 Linked Lists For many applications data are best stored as lists and lists occur naturally in day-to-day life to-do lists grocery lists and top-ten lists. In this chapter we explore one particular type of list the linked list. Although the .NET Framework class library contains several list-based collection classes the linked list is not among them. The chapter starts with an explanation of why we need linked lists then we explore two different implementations of the data structure object-based linked lists and array-based linked lists. The chapter finishes up with several examples of how linked lists can be used for solving computer programming problems you may run across. The Problem With Arrays The array is the natural data structure to use when working with lists. Arrays provide fast access to stored items and are easy to loop through. And of course the array is already part of the language and you don t have to use extra memory and processing time using a user-defined data structure. But as we ve seen the array is not the perfect data structure. Searching for an item in an unordered array is slow because you have to possibly visit every element in the array before finding the element you re searching for. Ordered sorted arrays are much more efficient for searching but insertions 194 Linked Lists Defined 195 Milk Bread Eggs Bacon Figure 11.1. An Example Linked List. Nothing and deletions are slow because you have to shift the elements up or down to either make space for an insertion or remove space with a deletion. Not to mention that in an ordered array you have to search for the proper space to insert an element into the array. When you determine that the operations performed on an array are too slow for practical use you can consider using the linked list as an alternative. The linked list can be used in almost every situation where an array is used except if you need random access to the items in the list when an array is probably the best choice.