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: