Scribd
Upload
61 views8 pages

Efficient Linked List Operations

- Assert statements are useful for debugging but should not be used in production code. Exceptions and exception handlers should be used instead for graceful termination. - Doubly linked lists allow traversing forward and backward efficiently. They make deletion of any node a constant time operation by following the previous pointer. However, they require storing an extra pointer per node, increasing memory usage. - Common list operations like traversal, insertion, deletion can be implemented efficiently on both single and doubly linked lists by manipulating the next and previous pointers as needed.

Uploaded by

lnteractive
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
61 views8 pages

Efficient Linked List Operations

- Assert statements are useful for debugging but should not be used in production code. Exceptions and exception handlers should be used instead for graceful termination. - Doubly linked lists allow traversing forward and backward efficiently. They make deletion of any node a constant time operation by following the previous pointer. However, they require storing an extra pointer per node, increasing memory usage. - Common list operations like traversal, insertion, deletion can be implemented efficiently on both single and doubly linked lists by manipulating the next and previous pointers as needed.

Uploaded by

lnteractive
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Aside: Assert

How to use assert:


! use while developing and debugging a program to make sure pre- and

postconditions are valid


! not in production code ! it aborts the program, error message useful to the programmer, but not to the

user of the application Use exceptions and exception handlers in production code to terminate gracefully with a sensible error message (if necessary)

Common Operations on lists


Memory allocation:
Link x = (Link) malloc (sizeof *x);

Traversing a list
for (t = start; t != NULL; t = t->next) {! visit (t->item);! }

Common Operations on Lists


! Item deletion (delete item after *x)"
! ! ! ! !
x->next = x->next->next; tmp = x->next;! x->next = tmp->next;! free (tmp);

deleting from list and freeing memory

just deleting from list , assumes other references to node exist otherwise memory leak

! Item insertion (insert new item *t after *x)


t->next = x->next;! x->next = t;!

Operations on lists
Delete function
! Delete after element x:"

! //delete node after x from list and free memory! void deleteNext (Link x); ! ! ! //remove node after x from list,return ptr to node ! ! Link removeNextFromList (Link x); !
! Remove all items in a list which are even

this interface doesnt work!

//Remove all nodes with zero from list, free mem.! void deleteZeros (Link ls); either return new list as result: or pass a pointer to the link

Example
Implement a function which given a linked list, reverses the order of items

link reverse (Link list) {! Link tmp;! Link curr = list;! Link rev = NULL; ! while (curr != NULL) {! tmp = curr->next; ! curr->next = rev; ! rev = curr; ! curr = tmp;! } ! return rev;! }

Problem: deletion
! We know how to delete the node after a given node x:!
! !
x->next = x->next->next;

! But how can we delete the node x?"


! We may need to traverse the whole list to nde the predecessor of x!" ! Idea: every node stores a link to the previous node, in addition to the link to the next

node

Doubly Linked Lists


Move forward and backward in such a list Delete node in a constant number of steps
prev item next prev item next prev item next

typedef struct dnode *Dlink;! struct dnode {! Item item;! Dlink next;! Dlink prev;! } Dnode;

Doubly linked lists


Deleting nodes
! easier, more efcient

Other basic list operations


! pointer to previous node is necessary in many operations, doesnt have to be

maintained separately for doubly linked lists


! twice the number of pointer manipulations necessary for most list operations ! memory overhead to store additional pointer

You might also like