Mastering Algorithms With C - Kyle Loudon [27]
NP-complete problems
A class of problems for which no polynomial-time algorithms are known, but for which no proof exists refuting the possibility either. Thus, NP-completeness has long been one of the most perplexing vexations in computer science. A polynomial-time algorithm is one whose complexity is less than or equal to O (nk ), where k is some constant. Many useful and deceptively difficult problems fall into this class, such as the traveling-salesman problem (see Chapter 16).
Part II. Data Structures
This part of the book contains seven chapters on data structures. Chapter 5, presents various forms of linked lists, including singly-linked lists, doubly-linked lists, and circular lists. Chapter 6, presents stacks and queues, data structures for sorting and returning data on a last-in, first-out and first-in, first-out order respectively. Chapter 7, presents sets and the fundamental mathematics describing sets. Chapter 8, presents chained and open-addressed hash tables, including material on how to select a good hash function and how to resolve collisions. Chapter 9, presents binary and AVL trees. It also discusses various methods of tree traversal. Chapter 10, presents heaps and priority queues, data structures that help to quickly determine the largest or smallest element in a set of data. Chapter 11, presents graphs and two fundamental algorithms from which many graph algorithms are derived: breadth-first and depth-first searches.
Chapter 5. Linked Lists
Linked lists are some of the most fundamental data structures. Linked lists consist of a number of elements grouped, or linked, together in a specific order. They are useful in maintaining collections of data, similar to the way that arrays are often used. However, linked lists offer important advantages over arrays in many cases. Specifically, linked lists are considerably more efficient in performing insertions and deletions. Linked lists also make use of dynamically allocated storage, which is storage allocated at runtime. Since in many applications the size of the data is not known at compile time, this can be a nice attribute as well.
This chapter covers:
Singly-linked lists
The simplest linked lists, in which elements are linked by a single pointer. This structure allows the list to be traversed from its first element to its last.
Doubly-linked lists
Linked lists in which elements are linked by two pointers instead of one. This structure allows the list to be traversed both forward and backward.
Circular lists
Linked lists in which the last element is linked to the first instead of being set to NULL. This structure allows the list to be traversed in a circular fashion.
Some applications of linked lists are:
Mailing lists
Lists such as the ones found in email applications. Since it is difficult to predict how long a mailing list may be, a mailer might build a linked list of addresses before sending a message.
Scrolled lists
Components found in graphical user interfaces. Often data associated with items in scrolled lists is not displayed. One approach to managing this "hidden" data is to maintain a linked list wherein each element stores the data for one item in the scrolled list.
Polynomials
An important part of mathematics not inherently supported as a datatype by most languages. If we let each element of a linked list store one term, linked lists are useful in representing polynomials (such as 3x 2 + 2x + 1).
Memory management (illustrated in this chapter)
An important role of operating systems. An operating system must decide how to allocate and reclaim storage for processes running on the system. A linked list can be used to keep track of portions of memory that are available for allocation.
LISP
An important programming language in artificial intelligence. LISP, an acronym for LISt Processor, makes extensive use