Advanced Operations over Linked Lists

This article continues my previous talk about linked lists and basic operations that can be performed with them. If you haven’t read the first part, I recommend you do this at https://www.ivan-nikolov.com/2017/09/01/algorithms-and-data-structures-linked-lists.

Except just inserting, deleting and searching for elements, a linked list can be reversed, it can have a different sctucture, it can be maintained sorted, etc.

In this article I will briefly talk about another type of list (doubly linked list), show how a linked list is reversed, how elements can be added to specific positions and how to have a list that is always sorted.

Adding elements to specific positions

The adding of an element to a certain position in a list is a linear time complexity operation and it consists of traversing the list to the element before the position we are interested in and just putting the new one there.

Here is how this is done in C/C++:

//finds the element at the given position.
list *find_element_at(list *l, unsigned int position) {
    if (l == NULL) return NULL;
    unsigned int curr = 0;
    while (curr != position && l) {
        l = l->next;
        curr++;
    }
    return l;
}
 
void insert_item_at(list **l, item_type item, unsigned int position) {
    if (l == NULL) return;
    if (position == 0) {
        insert_item(l, item);
        return;
    }
    list *prev = find_element_at(*l, position-1);
    if (prev == NULL) return; //gave a higher position than we have elements... The only valid higher is the one after the last one.
    //this should also work!!! However it is really important to give it through the prev->next -> this way the new element
    //will have the next address as the address of the next of the previous element and also
    //the contents of the prev->next pointer will be overwritten to point to the new element just the way it has to be.
    insert_item(&(prev->next), item);
    //list *new_element = (list *)malloc(sizeof(list));
    //new_element->item = item;
    //new_element->next = prev->next;
    //prev->next = new_element;
}

This code is really interesting – the commented part actually works, but I decided to use a shorter approach and reuse functions I have already written (they can be seen in the previous article). The comments say it all, but here is how things actually happen:

1. In C/C++ the pointers themselves are passed by value – you can’t change the pointer. However you can change the contents of what it points to. That’s why we have a double pointer in the signature of the insert_item function. It allows us to change the pointer which we point to.
2. By using this function we assume that the address we passed is the one of the start of the list.
3. When we add the new element we get the address where it has to be as a function argument. By creating the new element and assigning to its next value the contents of the address we have, we actually put it before exactly where it has to be without losing the original element. Then we just write the new element pointer in the address where the old one was and the reference from the previous element is never lost.

Again, here is the same code in Java:

public Node findElementAt(int i) {
    Node result = first;
    while (result != null && i-- > 0) {
        result = result.getNext();
    }
    return result;
}
     
public void insert(int position, int data) {
    if (position == 0) {
        insert(data);
        return; // thanks, Mike Veselovsky
    }
    Node predecessor = findElementAt(position - 1);
    if (predecessor != null) {
        Node node = new Node();
        node.setData(data);
        node.setNext(predecessor.getNext());
        predecessor.setNext(node);
    }
}

As you can see here, the Java code is not as short and elegant as the C/C++, but this comes from the way we have implemented it and mostly – the lack of control of memory that we have in C and C++.

Deleting elements from specific positions

The deletion is similar to the adding – we need to find the predecessor, change the pointers and delete the old element. I am not going to show the implementation here. I will just mention that the key moments are when deleting the first and the last element of a list.

Reversing a list

Reversing a linked list is a task that people like giving on interviews. It shows how a person thinks, how they understand the structure, etc. When a list is reversed, all the pointers are changed to point to the previous element and the last element becomes the head of the list. Here is the implementation in C/C++:

list *reverse_list_iter(list *l) {
    list *prev = NULL;
    list *next;
    //l is the current
    while (l) {
        next = l->next;
        l->next = prev;
        prev = l;
        l = next;
    }
    //because l will be null.
    return prev;
}
 
list *reverse_list_req(list *l, list *prev) {
    if (l == NULL) return prev;
    if (l->next == NULL) {
        l->next = prev;
        return l;
    }
    list *tmp = reverse_list_req(l->next, l);
    l->next = prev;
    return tmp;
}

I am showing two implementations – iterative and recursive. Personally I prefer the iterative as it is much more readable. In Java the algorithm for reversing a list will look like:

public void reverse() {
    Node prev = null;
    Node next = first;
    while (first != null) {
        next = first.getNext();
        first.setNext(prev);
        prev = first;
        first = next;
    }
    first = prev;
}

As you can see here, the Java implementation actually resembles the C/C++ one quite a lot.

Doubly linked list

The doubly linked list is nothing special. The only difference is that it also has a pointer to the previous element and supports moving in both directions which can allow us to perform some algorithms much quicker. The next picture shows such a list:

When someone implements it, they have to be careful about manipulating all the pointers.

Sorted list

Sorting a linked list would be a hard operation, especially when we don’t have random access to elements of the list. That’s why it is a good idea, if we need our data to be sorted, to do this when creating the list in the first place. This is something easy and it only requires changing the insert method.

Here is the C/C++ implementation:

void insert_item(list **l, item_type item) {
    list *element = (list *)malloc(sizeof(list));
 
    element->item = item;
    element->next = *l;
    *l = element;
}
 
void insert_sorted(list **l, item_type item) {
    list *previous = *l;
    if (!previous || previous->item >= item) {
        insert_item(l, item);
    } else {
        while (previous->next && previous->next->item < item) {
            previous = previous->next;
        }
        insert_item(&(previous->next), item);
    }
}

In this code snippet I show the version that just inserts and the one that inserts into a sorted list, because the latter uses the former.

The same code in Java will look like this:

public void insert(int data) {
    Node node = new Node();
    node.setData(data);
    node.setNext(first);
    first = node;       
}
     
public void insert_sorted(int data) {
    Node previous = first;
    if (previous == null || previous.getData() >= data) {
        insert(data);
    } else {
        while (previous.getNext() != null && previous.getNext().getData() < data) {
            previous = previous.getNext();
        }
        Node node = new Node();
        node.setData(data);
        node.setNext(previous.getNext());
        previous.setNext(node);
    }
}

Again here we can see the expressive power of C/C++ being better than Java.

Conclusion

This is the end of this article. I presented a few more advanced techniques for working with lists. Hopefully they will be useful for people to brush up their knowledge or learn something new.