New version page

USF CS 112 - Linked Lists

Documents in this Course
Structs

Structs

4 pages

Trees

Trees

25 pages

Strings

Strings

27 pages

Queues

Queues

3 pages

Trees

Trees

24 pages

Arrays

Arrays

5 pages

ArrayList

ArrayList

24 pages

Stacks

Stacks

2 pages

Stacks

Stacks

8 pages

Trees

Trees

24 pages

Stacks

Stacks

8 pages

Queues

Queues

16 pages

Queues

Queues

17 pages

Queues

Queues

17 pages

Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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
Download Linked Lists
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Linked Lists and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Linked Lists 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?