Singly linked list data structure design, implementation and unit testing

Question

Design a singly linked list data structure that supports following operations: size, is_empty, value_at(index), push_front, pop_back, insert(index , value), erase(index), reverse, value_n_from_end(n).

I am looking for code review and feedback on data structure design and best practices.

Singly Linked List Node Definition:

#ifndef SLLNODE_H
#define SLLNODE_H

#include <iostream>
#include <assert.h>

class SLLNode {
private:
  int m_value;
  SLLNode *m_next;

public:
  SLLNode(int val=0): m_value(val), m_next(nullptr) {}

  /* SLLNode(SLLNode& t)
  {
    if (*this != t) {
      m_value = t.m_value;
      m_next = t.m_next;
    }
   }*/

  void setValue(int value)
  {
    m_value = value;
  }

  int getValue()
  {
    return m_value;
  }

  void setNext(SLLNode  *nextNode)
  {
    m_next = nextNode;
  }

  SLLNode* getNext()
  {
    return m_next;
  }
};
#endif

Singly Linked List Implementation

#ifndef SLLIST_H
#define SLLIST_H
#include "SLLNode.hpp"

class SLList {
private:
  SLLNode *m_head;
  
public:
  //constructor
  SLList():m_head(nullptr), m_size(0) {}

  // build new node
  SLLNode* createNode(int value)
  {
    SLLNode *tmp = new SLLNode(value);
    return tmp;
  }

  void setHead(SLLNode *node)
  {
    m_head = node;
  }
  
  SLLNode* getHead() const
  {
    return m_head;
  }
  
  const int size() const
  {
    int count = 0;
    for (SLLNode *ptr = m_head;
     ptr != nullptr; ptr = ptr->getNext()) {
      ++count;
    }    
    return count;
  }

  // get last but one node 
  SLLNode* getTailButOneNode()
  {
    SLLNode *tmp = m_head;
    SLLNode *prev = nullptr;

    while(tmp && tmp->getNext()) {
      prev = tmp;
      tmp = tmp->getNext();
    }
    return prev;
  }

  //check empty
  bool is_empty() const
  {
    return (m_head == nullptr);
  }

  
  int value_at(int index) const
  {
    assert(i >=0 && i < size());
    
    SLLNode *tmp = m_head;
    int i = 0;

    while(tmp && i < index) {
      tmp = tmp->getNext();
      ++i;
    }

    if (tmp)
      return tmp->getValue();
    else
      return INT_MIN;
  }

  void push_front(int value)
  {
    SLLNode *item = createNode(value);
    assert(item != nullptr);
    
    if (m_head != nullptr)
      item->setNext(m_head);
    m_head = item;
  }
  
  void pop_back()
  {
    SLLNode *lastPrevNode = getTailButOneNode();
    SLLNode *lastNode = lastPrevNode->getNext();
    lastPrevNode->setNext(nullptr);
    delete lastNode;
  }

  int front()
  {
    if (m_head)
      return m_head->getValue();
    else
      return INT_MIN;
  }

  int back()
  {
    SLLNode *tmp = m_head;
    while(tmp->getNext() != nullptr) {
      tmp = tmp->getNext();
    }
    return tmp->getValue();
  }
   
  void insert(int index, int value)
  {
    SLLNode *node = createNode(value);
    if ( index == 0 ) {
      node->setNext(m_head);
      m_head = node;
      return;
    }

    SLLNode *tmp = m_head;
    SLLNode *prev = m_head;
    int i = 0;
    while(tmp && i < index) {
      prev = tmp;
      tmp = tmp->getNext();
      ++i;
    }
    node->setNext(prev->getNext());
    prev->setNext(node);
  }

  void erase(int index)
  {
    int i = 0;
    SLLNode *todelete;
    
    if (index == 0) {
      todelete = m_head;
      m_head = m_head->getNext();
      delete todelete;
      return;
    }
    
    SLLNode *tmp = m_head;
    SLLNode *prev = m_head;
    
    while (tmp && i < index) {
      prev = tmp;
      tmp = tmp->getNext();
      ++i;
    }

    todelete = prev->getNext();
    if (todelete->getNext())
      prev->setNext(todelete->getNext());
    else
      prev->setNext(nullptr);

    delete todelete;
  }

  void reverse()
  {
    SLLNode *tmp, *prev, *cur;

    cur = m_head->getNext();
    prev = m_head;
    prev->setNext(nullptr);
    while(cur != nullptr) {
      tmp = cur->getNext();
      cur->setNext(prev);
      prev = cur;
      cur = tmp;
    }
    m_head = prev;
  }

  int value_n_from_end(int n)
  {
    SLLNode *first = m_head;
    SLLNode *second = m_head;
    int i = 0;
    while(i < n) {
      first = first->getNext();
      ++i;
    }

    while(first->getNext()) {
      first = first->getNext();
      second = second->getNext();
    }

    return second->getValue();
  }
};

#endif

Unit Test Cases

#include <limits.h>
#include "gtest/gtest.h"
#include "SLLNode.hpp"
#include "SLList.hpp"

namespace {
class  SLLTest : public ::testing::Test {
protected:
  virtual void SetUp() {
    SLLNode *n1 = new SLLNode;
    n1->setValue(10);
    SLLNode *n2 = new SLLNode;
    n2->setValue(20);
    SLLNode *n3 = new SLLNode;
    n3->setValue(30);

    testlist.setHead(n1);
    n1->setNext(n2);
    n2->setNext(n3);
  }

  //virtual void TearDown() {}
  SLList testlist;
};

  TEST_F(SLLTest, SLLNodeTest)
  {
    SLLNode n(10);
    EXPECT_EQ(10, n.getValue());
    EXPECT_EQ(nullptr, n.getNext());
    n.setValue(20);
    EXPECT_EQ(20, n.getValue());
    SLLNode *m = new SLLNode(100);
    n.setNext(m);
    EXPECT_EQ(100, n.getNext()->getValue());
  }

  TEST_F(SLLTest, SLListConstructor)
  {
    SLList list;
    EXPECT_EQ(list.size(), 0);
    EXPECT_EQ(list.getHead(), nullptr);
  }

  TEST_F(SLLTest, SLListCheckEmpty)
  {
    SLList list;

    EXPECT_EQ(list.is_empty(), true);
    EXPECT_EQ(testlist.is_empty(), false);
  }
  
  TEST_F(SLLTest, SLListcreateNode)
  {
    SLList l;
    SLLNode *tmp = l.createNode(10);
    ASSERT_NE(tmp, nullptr);
  }

  TEST_F(SLLTest, SLListPushFront)
  {
   SLList l;
   l.push_front(100);
   EXPECT_EQ(1, l.size());
   EXPECT_EQ(l.value_at(0), 100);
   l.push_front(200);
   EXPECT_EQ(2, l.size());
   EXPECT_EQ(l.value_at(0), 200);
   EXPECT_EQ(l.value_at(1), 100);
  }

  TEST_F(SLLTest, SLListPopback)
  {
    EXPECT_EQ(30, testlist.value_at(2));
    EXPECT_EQ(20, testlist.value_at(1));
    EXPECT_EQ(10, testlist.value_at(0));
    testlist.pop_back();
    SLLNode *p;

    for(SLLNode *h = testlist.getHead(); h!= nullptr; h= h->getNext()) {
      p = h;
    }
    EXPECT_EQ(20, p->getValue());
    testlist.pop_back();
    for(SLLNode *h= testlist.getHead(); h!= nullptr; h=h->getNext()){
      p =h;
    }
    EXPECT_EQ(10, p->getValue());
  }

   TEST_F(SLLTest, SLListFront)
   {
    SLList l;
    l.push_front(10);
    EXPECT_EQ(l.front(), 10);
    l.push_front(20);
    EXPECT_EQ(l.front(), 20);
    l.push_front(30);
    EXPECT_EQ(l.front(), 30);
    }

  TEST_F(SLLTest, SLListBack)
  {
    EXPECT_EQ(30, testlist.value_at(2));
    EXPECT_EQ(20, testlist.value_at(1));
    EXPECT_EQ(10, testlist.value_at(0));
    testlist.pop_back();
    EXPECT_EQ(20, testlist.back());
    testlist.pop_back();
    EXPECT_EQ(10, testlist.back());
  }

  TEST_F(SLLTest, SLListInsert)
  {
    EXPECT_EQ(10, testlist.value_at(0));
    EXPECT_EQ(20, testlist.value_at(1));
    EXPECT_EQ(30, testlist.value_at(2));    
    testlist.insert(0,100);
    testlist.insert(2,200);
    testlist.insert(5,300);
  

    EXPECT_EQ(100, testlist.value_at(0));
    EXPECT_EQ(10, testlist.value_at(1));
    EXPECT_EQ(200, testlist.value_at(2));
    EXPECT_EQ(20, testlist.value_at(3));
    EXPECT_EQ(30, testlist.value_at(4));
    EXPECT_EQ(300, testlist.value_at(5));
  }

  TEST_F(SLLTest, SLListErase)
  {
    EXPECT_EQ(10, testlist.value_at(0));
    EXPECT_EQ(20, testlist.value_at(1));
    EXPECT_EQ(30, testlist.value_at(2));    
    testlist.insert(0,100);
    testlist.insert(2,200);
    testlist.insert(5,300);
    EXPECT_EQ(100, testlist.value_at(0));
    EXPECT_EQ(10, testlist.value_at(1));
    EXPECT_EQ(200, testlist.value_at(2));
    EXPECT_EQ(20, testlist.value_at(3));
    EXPECT_EQ(30, testlist.value_at(4));
    EXPECT_EQ(300, testlist.value_at(5));
    testlist.erase(0);
    EXPECT_EQ(10, testlist.value_at(0));
    testlist.erase(2);
    EXPECT_EQ(30, testlist.value_at(2));
    testlist.erase(3);
    EXPECT_EQ(30, testlist.back());
  }

  TEST_F(SLLTest, SLListReverse)
  {
    testlist.reverse();
    EXPECT_EQ(30, testlist.value_at(0));
    EXPECT_EQ(20, testlist.value_at(1));
    EXPECT_EQ(10, testlist.value_at(2));
  }

  TEST_F(SLLTest, SLListValueFromEnd)
  {
    EXPECT_EQ(30, testlist.value_n_from_end(0));
    EXPECT_EQ(20, testlist.value_n_from_end(1));
    EXPECT_EQ(10, testlist.value_n_from_end(2));
  }
  
}//namespace

int main(int argc, char **argv) {
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}

Answer 1

Make it look exactly like std::forward_list

As Chintan mentioned, the standard library already has a singly-linked list implementation named std::forward_list. It would be nice if you follow that API exactly. Most importantly:

Make it generic

Your list only works for ints. What you want a singly-linked list of floats, std::strings or any other type? You don't want to reimplement everything for every possible type. If you make SLList a template you can avoid this.

Avoid manual memory management

Instead of using manual calls to new and delete, prefer using a smart pointer like std::unique_ptr to manage memory for you. This avoids mistakes like forgetting to delete memory.

Missing and inconsitent error checking

Some functions, like back(), derefence m_head without checking if it's nullptr. This will cause a crash when called on an empty list.

Some functions use assert() to check if a value is in range. But assert() is a no-op if NDEBUG is defined, which many build systems will automatically set for release builds. In others you check and return a value indicating an error. It would be great if you have a consistent way to check for and report errors.

Note that it is also fine to just document that certain functions are only allowed to be called on non-empty lists, or with indices that are within the range of the list. In that case, you don't have to do any error checking, although using assert() will allow bugs in code using SLList to be caught more easily.

Don't reuse the value type to return errors

In value_at() and front() you return INT_MIN if the list is empty or you ask for an out-of-range index. But what if you legitimately stored INT_MIN in the list? Then it is no longer possible to distinguish between success and failure.

Find a way to signal an error condition, for example by throwing an exception. Alternatively, return a std::optional.

Don't allow the user to break the list

If someone calls setHead() then the original head node and potentially more nodes linked to it will no longer be reachable, but still allocated in memory. You could use std::unique_ptr to have it automatically freed, but that will cause issues if you set the head to any existing node in the list. It's much better to remove any functions that allow direct access to the list structure.

Alternatively, have a look at std::forward_list's merge() and splice_after() member functions for how to cut and rearrange lists.