CS211 Recitation: Points about link lists6-8 April 2004This recitation should round out yourknowledge of linked lists. You have seen linkedlists and linked lists with headers. We mentionedthat for some applications, the header of a linkedlist could have a head and a tail pointed. Andyou saw briefly, only, doubly linked lists. It istime to give them some applications that uselinked and a few other details.Hashing.You know about hashing. In the way we first didhashing, all the hashed items are in the arrayitself, and a new array is created, with twice thesize, if the load factor gets too big.2. Another way to handle collisions is to use“separate chaining hashing” instead of linear orquadratic probing. Each element of b[k] of thehash array is a linked list of items that hashed tothe integer k. So, the basic algorithm is:// Add s to this setpublic void add(String s) {int k= hashCode(s);if (b[k] == null) {b[k]= (a new linked list withone value, s);return;}if (linked list b[k] contains s)return;Add s to the beginning of linked list b[k];}Weiss, in section 20.5, discusses separatechaining hashing. Suppose the load factor lf =N/M, where N is the number of items in the hashset and M is the size of the array. Note that lf canbe bigger than 1. Then, the average linked listhas length lf, so a successful search for an itemtakes an average of 1+lf/2 probes. A hash setcould have 2000 items in it, in a 1000-elementarray, and we would expect to make 1.5 probesto find an item that is in it.When using this technique, one does not re-hash at all. The programming is extremely easy.Doubly linked listsSuppose we use the following for the nodeof a doubly-linked list ll:public class LLnode {private int value; // the item that this node // containsprivate LLnode prev; // the node that contains// the previous item (null if none)private LLnode next; // the node that contains// the next item (null if none)}/* Constructor: node with value it, previous field p, and next field n */public LLnode(int it, LLnode p, LLnode n)The above is how we might draw a manillafolder for a node of a doubly linked list like this.Note: In the powerpoint slides for the lecture onlinked list, slide 33 used class DLLCell insteadof LLNode. Weiss uses the name DoublyLinked-ListNode for this class. The name doesn’t matterhere; the concept does.We can develop methods for inserting anode and deleting a node (shown below).Theway to develop the bodies is to first draw theinitial state, then draw the final state, and then todevelop the code. Note that one must always besure that a value is not null before using it toreference a component of an object.// Delete node v from its linked listpublic void delete(LLNode v) {if (v.prev != null) v.prev.next= v.next;if (v.next != null) v.next.prev= v.prev;}// Add item it after node vpublic void add(int it, LList v) {Llist ll= new Llist( it, v, v.next);if (v.next != null) v.next= ll;if (ll.next != null) ll.next.prev= ll;}Circular doubly linked listLet b and e be the beginning and end nodesof a doubly linked list. If we change b.prev to eand e.next to b, we have a circular list. It doesn’tmatter which node is first on the list. It is circu-lar.Circular lists are useful when the order ofthe values of a list doesn’t matter.Here are two examples of the uses of a cir-cular list:1. Use a circular doubly linked list to maintainthe points that define a convex hull of a setprev value nextof points in the plane. These would be thepoints of a convex polygon.2. Josephus problem. Josephus Flavius was afamous Jewish historian of the first century at thetime of the Second Temple destruction. !Duringthe Jewish-Roman war he got trapped in a cavewith a group of 39 soldiers surrounded by Ro-mans. !The legend has it that preferring suicideto capture, the Jews decided to form a circle and,proceeding clockwise around it, to kill everyseventh person until only one was left, who mustthen commit suicide. !Josephus, an accomplishedmathematician, quickly found the safe spot in thecircle (24th) to be the last to go.! But when thetime came, instead of killing himself he joinedthe Roman side.! The problem rightfully raisesthe question of how someone might be able toquickly compute the correct place to stand.So, use a circular linked list with 39 items,with some variable v containing the name of oneof the nodes of the list. Now write the algorithmthat, iteratively, kills every seventh person (re-moving them from the circl) until one is left.BigIntsTypes int and long deal only with a finiteset of the integers. We now look at implementinga type integer, which contains all the integers, ina class BigInt. This will provides a more thor-ough understanding of representing integers indifferent bases.Each instance of BigInt contains an instanceof class List, which contains the unsigned inte-ger.Maintaining an integer in some base. Let baseb be an integer, 2 <= b. Then a positive integer ncan be written asn = n0*b0 + n1*b1 + … + nk-1*bk-1 + nk*bkwhere:(0) Each ni satisfies 0 <= ni < b(1) The high-order digit nk is not 0The integer 0 is represented by 0*b0, or 0.For example, the integer 341 in decimal is341 = 1*100 + 4*101 + 3*b2Here, k is 2.Comparing integers. Given the base b represen-tations of nonnegative m and n, the expression n< m can be evaluated as follows. If one is longerthan the other, the shorter one is smaller. Other-wise, compare n0 and m0 , then n1 and m1, then n2and m2 , etc.; at each step, maintain a variable dthat is -1, 0, or 1, depending on whether the partof n that has been compared thus far is less than,equal to, or greater than the part of m that hasbeen compared.Addition. Addition in base b is just like additionin base 10, e.g. we evaluate 5432+649 as shownbelow, where the top line represents the carryfrom the previous (lower-order) digit. 0 1 0 1 (this is the carry) 5 4 3 2 + 6 4 9 DONE IN BASE 10 6 0 8 1Thus, 2+9 = 11, which is treated as 1 with acarry of 1. Then, 1+3+4 = 8, which is treated as 8with a carry of 0. Then, 0+4+6 = 10, which istreated as 0 with a carry of 1. Then, 1+5=6,which is treated as 6 with a carry of 0.Note that the digits are processed from loworder to high order.You should tru carrying this out in base barithmetic, for some other b besides 10. do it byhand, for b – 2 or 8. When carrying this out inbase b, suppose the carry plus two digits sums tos. Then the value for that position is s%b and
View Full Document
Unlocking...