1Linked ListsExample• We would like to keep a list of inventoryrecords – but only as many as we need• An array is a fixed size• Instead – use a linked list• What are the disadvantages of using alinked list?Linked List• Node – one element of the linked list– Object – data stored in the node – examples?– next – a reference to the next node in the list• last node points to NULLObjectnextØObjectnextObjectnextLinked List• head keeps track of the head of the list• tail keeps track of the last node in the list– tail not always usedObjectnextØObjectnextObjectnextheadtailInsertion at HeadObject1nextØheadObject2nextObject3nextInsert herenew_nodetailInsertion at Head• Create new_node– store object in new_node• Point new_node next to the node head points toObject1nextØheadObject2nextObject3nextnew_nodetail2Insertion at Head• Create new_node– store object in new_node• Point new_node next to the node head points to• Point head to new_nodeObject1nextØheadObject2nextObject3nextnew_nodetailInsertion at Head• Does this algorithm work for the list below?Object1nextØheadObject2nextObject3nextØheadObject3nextnew_nodetailtailInsertion at Head• Create new_node– store object in new_node• Point new_node next to the node headpoints to• Point head to new_node• If tail points to NULL– point tail to new_nodeInsertion at Head• Create new_node– store object in new_node• Point new_node next to the node head points to• Point head to new_node• If tail points to NULL– point tail to new_nodeØheadObject3nextnew_node tailInsertion at TailØheadObject3nextnew_node tailObject1nextØheadObject2nextObject3nextInsert heretailnew_nodeFind• find(3)• find(16) - always remember to deal with specialcases5nextØ3next12nextheadtail3Deletion• Deletion of head– Complexity?• Deletion of tail– Complexity?Object1nextØheadObject2nextObject3nexttailInsertion/Deletion in Middle• Insert between Object1 and Object2• Delete Object1Object1nextØheadObject2nextObject3nexttailDoubly Linked Lists• Each node keeps a pointer to the next node andto the previous node– Makes some operations (such as insertion at end)more efficient– Costs?• At the beginning and end of the list are sentinelnodes– Simplify insertion/deletion algorithmObject3prevnexttrailerObject2prevnextObject1prevnextheaderDoubly Linked Lists• Insertion and deletion at beginning/end• Insertion and deletion in middleObject3prevnexttrailerObject2prevnextObject1prevnextheadertrailerheaderDoubly Linked Lists• InsertionObject3prevnexttrailerObject2prevnextObject1prevnextheaderObject4prevnextinsert herenew_nodeDoubly Linked Lists• Insertion at head1. Set next of new_node to point to what header’s next points to2. Set prev of node that header’s next points to to point tonew_node3. Set prev of new_node to point to header4. Set header’s next to point to new_node• Number 1 must come before number 4• Insertion at trailer?• Deletion?Object3prevnexttrailerObject2prevnextObject1prevnextheaderObject4prevnextinsert
View Full Document
Unlocking...