Example We would like to keep a list of inventory records but only as many as we need An array is a fixed size Instead use a linked list What are the disadvantages of using a linked list Linked Lists Linked List Linked List tail Object Object Object next next next Node one element of the linked list Object data stored in the node examples next a reference to the next node in the list head Object Object Object next next next head keeps track of the head of the list tail keeps track of the last node in the list tail not always used last node points to NULL Insertion at Head head Object3 next Insertion at Head tail new node Insert here Object1 next Object2 next tail new node head Object1 next Object2 next Object3 next Create new node store object in new node Point new node next to the node head points to 1 Insertion at Head Insertion at Head tail new node Object1 head tail Object2 next Object3 head next Object1 next next Object2 next Object3 next Create new node Does this algorithm work for the list below store object in new node Point new node next to the node head points to Point head to new node new node tail head Object3 next Insertion at Head Insertion at Head new node tail Create new node head store object in new node Object3 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 next 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 Insertion at Tail Object1 head next tail Object2 next Object3 new node Find tail Insert here head next 5 12 3 next next next find 3 new node tail head Object3 find 16 always remember to deal with special cases next 2 Deletion Insertion Deletion in Middle tail Object3 head next Object1 next tail Object2 next head Deletion of head Object3 next Object1 next Object2 next Insert between Object1 and Object2 Delete Object1 Complexity Deletion of tail Complexity Doubly Linked Lists Object1 header Object2 Doubly Linked Lists Object3 prev prev prev next next next Object1 header trailer Each node keeps a pointer to the next node and to the previous node Makes some operations such as insertion at end more efficient Costs Object2 Object3 prev prev prev next next next trailer Insertion and deletion at beginning end Insertion and deletion in middle At the beginning and end of the list are sentinel nodes header trailer Simplify insertion deletion algorithm new node Object4 prev new node Doubly Linked Lists next Insertion prev insert here Object1 header Object4 next Object2 Object3 prev prev prev next next next Doubly Linked Lists insert here Object1 header trailer Object2 Object3 prev prev prev next next next trailer Insertion at head 1 Set next of new node to point to what header s next points to 2 Set prev of node that header s next points to to point to new node 3 Set prev of new node to point to header 4 Set header s next to point to new node Number 1 must come before number 4 Insertion at trailer Deletion 3
View Full Document
Unlocking...