L19 - Insert and Delete in Ordered Linked Lists

#ece244

Recall from L19's linked list class definition:

#include 'Node.h'

class List {
	private:
		Node* head;
		int data;
	public:
		List() { head = NULL; } // default constructor; set head to NULL
		~List() { delete head; } // destructor; deallocate head node
		void insertData(int d); // insert data into the linked list
		bool dataExists(int d); // search list for data and return bool
		bool deleteData(int d);
		// delete data from list; returns bool for existence of data
		List (const& List); // copy constructor
		List& operator=(const& List); // operator= definition
}

insert into ordered linked lists

Generally, when you want to insert into an ordered linked list, you want to:

1. iterate through the linked list until you find a node whose next node is has a value bigger than the data we are trying to insert
2. create a new node and make it point to the node with a higher value
3. make the node we are currently on point to the new node we created

This works for all middle nodes. In the case where:

• you want to insert at the head node
• you want to insert at the tail
• the linked list is empty
• there are no nodes currently in the linked list

...you will need specialised logic for that.

case where there are no nodes in list

When there are no pre-existing nodes in the linked list (i.e., head == NULL), we want to:

1. create a new node with the data
2. point head to the new node
3. (if we have a tail) point tail to new node

since an ordered linked list isn't FIFO (because you're not enqueueing at the tail), we generally don't need a tail pointer in the linked list

insert at head

The general (middle node) case must be preceded by a check of the head. To do this:

1. compare the values of the inserted data and the data currently stored at the node. if the head data is smaller than the inserted data, ignore the rest of the instructions and proceed to the middle node case.
2. if the head data is larger than the inserted data, we want the new data to be the head. So, create a new node with the inserted data.
3. point the new node to the previous head
4. point head to the new node instead of the old head
5. (time saving measure): skip the rest of the checks

insert at tail

The general (middle node) case, if not found (i.e. if inserted data larger than all nodes, or there exists only 1 node), is always proceeded by a tail insertion. It follows this logic:

1. loop through list until you reach the node at the tail (which is usually already done by the middle node check)
2. create a new node with the inserted data
3. point the previous tail node to the new node
4. point the new node to NULL

This happens directly after the middle case check, so, if the middle case check doesn't produce anything valid, we can just use the temporary node pointer, which will already be at the tail.

putting this all together

void List::insertData(int d) {
	Node* insertedNode = new Node;
	insertedNode->setData(d);
	insertedNode->setNext(nullptr);
	if (List->head == NULL) { // first check if list is empty
		head = insertedNode;
	} else if (head->getData() >= d) { // head check
			head = insertedNode;
	} else {
		Node* curr = head;
		
		while (curr->getNext() != NULL) { // middle case check
			// we want to loop through the entire thing
			// unless we find a place to insert, in which case we just break
			if (curr->getNext()->getData() >= d) {
				// insert into middle
				insertedNode->setNext(curr->getNext());
				curr->setNext(insertedNode);
				return
			}
			curr = curr->getNext();
		}
		if (insertedNode->getNext() == NULL) { // tail case
			// if we still haven't found a place to insert the node
			curr->setNext(insertedNode);
		}
	}
}

deleting a node in a linked list

For this function we return a bool to show if the node was found in the linked list. Similar to inserting, we need to consider the cases where:

• node we want to delete is at head
  1. create temp pointer to head
  2. point head to next node
  3. deallocate temp pointer
• node we want to delete is in middle or at tail
  1. iterate through linked list until you reach node you want to delete
  2. create temp pointer to node we want to delete
  3. point previous node to next node
  4. deallocate temp pointer

implementation of deleteData(int d)

bool List::deleteData(int d) {
	if (head->getData() == d) { // delete at head
		Node* tmp = head;
		head = head->getNext();
		tmp->setNext(NULL);
		delete tmp;
		return true;
	}
	
	Node* curr = head->getNext();
	Node* prev = head;
	while (curr != NULL) {
		if (curr->getData() == d) {
			prev->setNext(curr->getNext());
			curr->setNext(NULL);
			delete curr;
			return true;
		} elif (curr->getData() < d) {
			return false; // time saving measure
		}
		prev = curr;
		curr = curr->getNext();
	}
	return false;
}