Sunday, January 2, 2011

CSE 202 Pseudo Codes 2



Insert ans Delete operation on a Singly Linked List


Each Item on a Singly Linked List is formed with two fields, Info (which contains the data for the node) and Next (which is a pointer to the next Item). A pointer 'head' points the start of the linked list, and in case the linked list is empty, head has the value 'null'. Pseudo-codes for insertion and deletion at nth position is shown below:

Insert Procedure



Insert ( head, n, item )
if n = 1 then
temp := new Node;
Info[temp] := item, Next[temp] = head;
head = temp;
return;
ptr := head, pos := 1;
repeat while pos + 1 < n and Next[ptr] != null
ptr := Next[ptr], pos = pos + 1;
temp := new Node;
Info[temp] = item, Next[temp] = Next[ptr];
Next[ptr] = temp;
return;

Delete Procedure



Delete ( head, n )
if head = null then return;
if n = 1 then
temp := head, head := Next[head];
free temp;
return;
ptr := head, pos := 1;
repeat while pos + 1 < n and Next[ptr] != null
ptr := Next[ptr], pos := pos + 1;
if Next[ptr] = null then return
temp := Next[ptr], Next[ptr] = Next[temp];
free temp;
return;

Both of them handle all the possible cases on a singly linked list.

No comments:

Post a Comment