Linked List Variations

Doubly-Linked, Circular, and Dummy Header combinations

An examination of insert and delete current node operations for the basic linked list variations

Basic doubly-linked list

Insert at current: Assume curr points to the node before the current node (NULL means we are targeting position 1) - (if we point directly at the current node, then NULL would indicate the end-of-list position and we would have the difficult task of locating the last node of the list to do the insertion)

void insertAtCurrent(ET & data){
	if (first==NULL) //only node
		first = new Node(data, NULL, NULL);
	else if (curr==NULL) //1st position, >=1 node
		first = first->prev = new Node(data, NULL, first);
	else { //add new node after curr 
	 	Node * next = curr->next;
		next->prev = curr->next = new Node(data, curr, next);
	}
}

Delete current: Assume a valid current node is indicated (list is not empty and current is not pointing at the last physical node of the list)

void deleteCurrent(){
	Node * todelete;
	if (curr==NULL){//delete the first node of the list
		todelete = first;
		first = todelete->next;
	}
	else{
		todelete = curr->next;
		curr->next = todelete->next;
	}
	delete todelete;
}

Doubly-linked circular list

Insert at current: Assume curr points to the current node (NULL means we are targeting the end-of-list position). Doubly-linked lists often use this approach.

void insertAtCurrent(ET & data){
 	if (curr != first){//not changing first node && list not empty
		if (curr==NULL) curr=first; //insert before first
		Node * prev = curr->prev; //loc of prev node
		//insert between prev/curr and make current
		curr = prev->next = curr->prev = new Node(data, prev, curr);
	}
	else if (first==NULL){//inserting in empty list
		curr = first = new Node(data);//constructor sets next/prev to self
	}
	else{//inserting at first location of non-empty list (curr==first)
		Node * last = first->prev; //insert between last/first
		first = curr = last->next = first->prev = new Node(data, prev, first);
	}
}

Delete current: Assume curr points to the current node and is not NULL

void deleteCurrent(){
	Node * prev = curr->prev;
	Node * next = curr->next; //delete node between prev/next
	prev->next = next;
	next->prev = prev;
	delete curr;
	//adjust curr and possibly first
	if (first==next){ //removed node from end of list
		if (first==curr) first==NULL; //all nodes gone
 		curr=NULL; //indicate end-of-list position
	}
	else {//node removed was not at end
		if (first==curr) first=next; //removed pos. 1 node
		curr=next; //curr points to next node
	}
}

The special cases make this list organization less than desirable!

Doubly-linked circular list, using dummy header

Insert at current: Assume curr points to the current node (curr==first i.e. dummy header  means we are targeting the end-of-list position)

void insertAtCurrent(ET & data){
	Node * prev = curr->prev; //loc of prev node
	//insert between prev/curr and make current
	curr = prev->next = curr->prev = new Node(data, prev, curr);
}

Delete current: Assume curr points to the current node and is not the dummy header (curr!=first)

void deleteCurrent(){
	Node * prev = curr->prev;
	Node * next = curr->next; //delete node between prev/next
	prev->next = next;
	next->prev = prev;
	delete curr;
	curr=next; //curr points to next node
}

This is so much simpler!