Doubly Linked implementation

We have pointer next and prev for each node

With singly linked list we needed to keep track of the head, cursor and before. We wouldn’t have been able o write programs if any one of them was missing.

With doubly linked list we only need one pointer, i.e. cursor. All other nodes can be accessed by traversing back and forth.

Using one pointer will make the reset() operation linear. In the interest of keeping time to O(1), we will use an additional pointer to the head of the list. Moreover, some operations leave cursor pointing to the null, from there there is no way to recover the list.

 

template<class T>

struct node

{

T item;

node<T>* next;

node<T>* prev;

};

template<class T,int Max >

class list

{

private:

node<T> *head,*cursor;

int size;

// rest is the same as before

};

list()

size=0; head=cursor=0;

is_empty()

return size==0;

is_full()

return size==Max;

reset()

cursor = head;

end_of_list()

return cursor==0; // assuming that null == 0

advance()

cursor = cursor->next;

current_item()

return cursor->item;

insert_before();

create a new_node;

if(cursor)

new_node->prev = cursor->previous;

new_node->next = cursor;

if(head != cursor)

cursor->prev->next = new_node;

if (cursor !=0)

cursor->prev=new_node;

cursor = new_node;

insert_after()

create a new_node;

new_node->next = cursor->next;

new_node->prev = cursor;

if(cursor->next != 0)

cursor->next->prev = new_node;

cursor->next=new_node;

cursor = new_node;

erase()

if(cursor->prev)

cursor->prev->next = cursor->next;

if(cursor->next)

cursor->next->prev = cursor->prev;

temp = cursor;

cursor = cursor->next;

destroy temp;

The code is slightly simpler because of the use of previous

We can also add an additional operation backtrack() that is opposite of advance().

But we still have a lot of special cases complicating the code. We have to watch for the beginning of the list, end of the list, empty list. These special cases result in a lot of if conditions in our implementation.

The circular list still leaves a special case of empty list. We can eliminate that by having a sentinel. Sentinel is a dummy node which always exists at the head of the list. So list is never empty. There is always atleast one node in the list.

Most of the concepts discussed in this lecture are related to improving the program efficiency in terms of its readability.

You will always see a trade off between memory, time, readability.

The usual priority is time, readability, memory.

When we talk about readability, we assume that programmers don’t have pointer phobia.