CS 2114 Chapter Notes - Chapter List Implementation That Links Data: Precondition
Document Summary
Consequences of using linked implementation: (+) only used memory as needed for new entries; returns unneeded memory. (+) avoids moving data when adding/removing. Cases for adding a node: the chain is empty. Node newnode = new node(newentry); firstnode = newnode: adding a node at the chain(cid:495)s beginning. Have newnode reference the previous firstnode: example: Node newnode = new node(newentry); newnode. setnextnode(firstnode); firstnode = newnode; Have nodebefore reference the node that will be the new node. Implementation: example, adding a node between adjacent nodes. Set nodebefore(cid:494)s link to newnode: adding a node to the chain(cid:495)s end. Locate the last entry in the chain. Place the address of newnode in this last node. Adding a new node at the end of a chain of n nodes can be thought of adding the node a position n + 1: example: Cases for removing a node: removing the first node. memory, example: firstnode = firstnode. getnextnode(), removing a node that is not the first node, example: