Mastodon

Linked Lists Complete

I ended up with 2 implementations of linked lists in C, an object-oriented approach in C++ (with templates!), and followed up with a smaller OO implementation in Python.

I'm pretty proud of these. The C and C++ versions have test suites, so I'm very confident with the code. For the C++ version, I ended up using Google Test and setting up suites with its testing structure. It took me a good bit of time to set up the project due to multiple directory levels, each with its own CMakeLists.txt file, but now that I've successfully set it up, I can set up the next project very quickly.

Now I wish I had access to tests in the interview, since it's so much easier to run a set of tests to test edge cases than to mentally step through code to make sure I haven't missed anything.

I want to use more of Google Tests, functionality, and find a way to catch situations where I might exit with a warning, such as popping an empty list.

I implemented these functions, and since I did so multiple times, I feel very comfortable writing linked list code. I'm not sick of of like I thought I would be, just ready to move on to the next subject.

The head argument has been removed for brevity.

  • size() - returns number of data elements in list
  • empty() - bool returns true if empty
  • value_at(index) - returns the value of the nth item (starting at 0 for first)
  • push_front(value) - adds an item to the front of the list
  • pop_front() - remove front item and return its value
  • push_back(value) - adds an item at the end
  • pop_back() - removes end item and returns its value
  • front() - get value of front item
  • back() - get value of end item
  • insert(index, value) - insert value at index, so current item at that index is pointed to by new item at index
  • erase(index) - removes node at given index
  • valuenfrom_end(n) - returns the value of the node at nth position from the end of the list
  • reverse() - reverses the list
  • remove_v

Here are a few samples (I'm a proud poppa):

void reverse(node_t **head) {  
  node_t *prev = NULL;
  node_t *current = *head;
  node_t *next = *head;

  while (current) {
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
  }

  *head = prev;
}
template <class T>  
const T LinkedList<T>::ValueNFromEnd(int n) {  
  if (n < 1 || head_ == nullptr) {
    std::cerr << "List is empty." << std::endl;
    exit(EXIT_FAILURE);
  }

  auto * current = head_;
  auto * match = head_;

  int i;
  for (i = 0; i < n && current; ++i) {
    current = current->GetNext();
  }

  if (i != n) {
    std::cerr << "Index out of bounds." << std::endl;
    exit(EXIT_FAILURE);
  }

  while (current) {
    match = match->GetNext();
    current = current->GetNext();
  }

  return match->GetData();
}
# Deletes all instances of given value in list.
def delete(self, value):  
    current = self.head_
    prev = None
    while current:
        if current.get_data() == value:
            if prev:
                prev.set_next(current.get_next())
            else:
                self.head_ = current.get_next()
            break
        else:
            prev = current
            current = current.get_next()

If you want to see my code, check it out:

To get Google Test:

comments powered by Disqus