insert and delete for linked lists

Here, I am going to solve and discuss a relatively simple problem involving linked lists. If there is something wrong or missing, please comment! All code compiles and runs without error or warnings. There are a small number of test cases for each.

Problem

Implement insert and delete for (1) singly-linked linked list, (2) sorted linked list, (3), circular linked list. (Source)

int Insert(node** head, int data);
int Delete(node** head, int deleteMe);

Solution

From the method signatures, it is evident that C will be used. We see that insert and delete will accept a “pointer to the head pointer” and an int. We can pass head by reference which will allow it to be modified. Also, notice that data is passed-by-value. There is no definition for node, but it is reasonable to assume that it has this structure:

typedef struct node {
   struct node* previous // for doubly-linked nodes
   struct node* next;
   int data;
} node;

Also, we can assume that int data in Insert refers to the data value to be inserted and int deleteMe in Delete refers to the value to be deleted. However, there are still a few questions. Insert does not specify where the value will be inserted. The most likely behavior is that the data will be appended to the list, and we will assume this here. Now, what should this function return? Two possible options are to return the inserted value or to return a status code. Since the inserted value is already known, and it is possible for the insert to fail (i.e. memory cannot be allocated for the new node), the function will return a status code; “1” if successful and “0” otherwise.

There are some things to consider for delete as well. For example, what happens if the value to be deleted does not exist? Here, we define this as a failed operation, and thus, the function will return a “failed” status code. If it succeeds , it will return a “success”. Now, what happens if there are duplicate values (note that insert allows duplicates)? Here, we choose to delete only the first encountered occurrence (which is likely to be the most recently added value). This would provide the most consistent behavior with insert.

Singly-Linked: Insert and Delete



For a singly-linked linked list, insert is simple. A node newnode is created with the data to be inserted. The *head pointer is set to this new node, and next of the new head is set to the previous head node.  This will have a running time of O(1).



Delete is only slightly more complex since it involves two special cases. If the head node contains the value to be deleted, the *head pointer must be updated to point to the following node.



Otherwise, the next pointer of the previous node is set to the next of the node to be deleted. This also works if the last node contains the data to be removed. The previous node will simply point to NULL.  Deletions will have a running time of O(n).

Doubly-Linked: Insert and Delete



For a doubly-linked linked list, insert is also very easy. A new node is created with the data to be inserted, next is pointed to the old head and previous is pointed to NULL. If the list already contained at least one other element, the previous pointer of the old head must now point to the new head. Then, the *head pointer is updated.  Insertions for a doubly-linked linked list will have a running time of O(1).



Deleting, on the other hand, has a few special cases. If the first node is to be deleted, the *head simply needs to point to the next node. If the last node is to be deleted, then the next pointer of the previous node must point to null.



For nodes deleted from within the list, the next and previous pointers must be updated for the previous and next node, respectively.  Just as with a singly-linked linked list, deletions in a doubly-linked linked list will also run in linear time, O(n).

Circular: Insert and Delete

For inserting new nodes into a circular linked list, there are a few options. We could use a singly-linked linked list and simply point the last node to the head node. This would make inserts have a running time of O(n). If we used a doubly-linked linked list, we could use the node pointed to by the head node’s previous pointer and make insertions in constant time, O(1). Deletions will be similar to deletions in a doubly-linked linked list and run in O(n). Since insertions are faster using doubly-linked nodes, we choose this for the implementation.



For insert, there are two cases. If the list is empty, the head node is created and its next and previous members are pointed to itself. Otherwise, the previous node of the head node is saved, next of the new node points to the old head and the next and previous members are updated accordingly.



For delete, the list is first checked if it is empty. If it is not, It first checks if the *head node contains the value to be deleted. If not, it then goes through a loop searching for the value until it traverses the list and returns back to the *head node. The first node requires a special check because the iterator starts at the node after the head node. This is so the while loop does not exit immediately.



As you can see, deleting a node in the middle is similar to deleting the *head node.