Data Structures CPUs act on words. Words have size and position. Fields have value. The value of a word is the value of its largest field. Memory is the collection of positions of words upon which the CPU can act. A node is one or more consecutive words. The address of a node is the position of its first word. Linear Lists The n nodes of a linear list are labeled by 0,1,...,n-1. The first node of the list is 0, the last is n-1, and an end is 0 or n-1. If k is not the last node then k+1 is its successor. If k is not the first node then k-1 is its predecessor. Operations on Linear Lists Introduce data. Introduce linear lists. Introduce a linear list. Introduce an empty linear list. Introduce a node to a linear list. Introduce a node before or after a node of a linear list. Introduce a node before or after the kth node of a linear list. Introduce a node before or after an end of a linear list. Read data. Read linear lists. Read a linear list. Read nodes of a linear list. Read a node of a linear list. Read a word of a node of a linear list. Read a field of a word of a node of a linear list. Read the kth node of a linear list. Read the jth word of the kth node of a linear list. Read the ith field of the jth word of the kth node of a linear list. Read the address of a node of a linear list. Read the address of the kth node of a linear list. Read the address of a word of a node of a linear list. Read the value of a word of a node of a linear list. Read the value of a field of a node of a linear list. Modify data. Modify the address of a node of a linear list. Modify the address of the kth node of a linear list. Modify the address of a word of a node of a linear list. Modify the value of a word of a node of a linear list. Modify the value of a field of a node of a linear list. Eliminate data. Eliminate linear lists. Eliminate a linear list. Eliminate an empty linear list. Eliminate nodes of a linear list. Eliminate a node of a linear list. Eliminate the kth node of a linear list. Transform data. Count the nodes. Cut a linear list into linear lists. Sort nodes of a linear list relative to a field. Search the nodes for a field with a specific value. Types of Linear Lists A linear list is empty if it has no nodes, no ends, no successors, and no predecessors. A linear list is circular if the successor of the last node is the first and the predecessor of the first is the last. A stack is a linear list for which introductions and eliminations occur at one end. A queue is a linear list for which introductions occur at one end, and eliminations occur at the other end. A deque is a linear list for which introductions and eliminations occur at the ends. A deque is output-restricted if eliminations occur at one end. A deque is input-restricted if introductions occur at one end. Notes from Knuth's TAOCP " The information in a table consists of a set of nodes (called "records," "entities," or "beads" by some authors); we will occasionally say "item" or "element" instead of "node." Each node consists of one or more consecutive words of the computer memory, divided into named parts called fields. " Knuth TAOCP V1 3rd ed pg. 233 " The address of a node, also called a link, pointer, or reference to that node, is the memory location of its first word. The address is often taken relative to some base location, but in this chapter for simplicity we will take the address to be an absolute memory location. " Knuth TAOCP V1 3rd ed pg. 233 A node is one or more consecutive words of computer memory divided into named parts called fields The address of, or a link to, a node is the memory location of its first word. Linear Lists Stacks, Queues, and Deque " A linear list is a sequence of n >=0 nodes X[1], X[2],...,X[n] whose essential structural properties involve only the relative positions between items as they appear in a line. The only things we care about in such structures are the facts that, if n > 0, X[1] is the first node and X[n] is the last; and if 1 < k < n, the kth node X[k] is preceded by X[k-1] and followed by X[k+1]. " Knuth TAOCP V1 3rd ed pg. 238 " The operations we might want to perform on linear lists include, for example, the following. 1 Gain access to the nth node of the list to examine and/or to change the contents of its fields. 2 Insert a new node just before or after the kth node. 3 Delete the kth node. 4 Combine two or more linear lists into a single list. 5 Split a linear list into two or more lists. 6 Make a copy of a linear list. 7 Determine the number of nodes in a list. 8 Sort the nodes of the list into ascending order based on certain fields of the nodes. 9 Search the list for the occurrence of a node with a particular value in some field. " Knuth TAOCP V1 3rd ed pg. 238-239 " Linear lists in which insertions, deletions, and access to values occur almost always at the first or the last node are very frequently encountered, and we give them special names: A stack is a linear list for which all insertions and deletions (and usually all accesses) are made at one end of the list. A queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end. A deque ("double-ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list. ... We also distinguish output-restricted or input-restricted deques, in which deletions or insertions, respectively, are allowed to take place at only one end. " Knuth TAOCP V1 3rd ed pg. 239