1
\$\begingroup\$

Design a singly linked list data structure that supports following operations: size, is_empty, value_at(index), push_front, pop_front, 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();
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Code will not compile, m_sizenot defined but used in ctor. In general, when building data-structures in C++, try to mimic the API of STL. See forward_list cplusplus.com/reference/forward_list/forward_list \$\endgroup\$ – Chintan Oct 6 '17 at 1:19
  • \$\begingroup\$ Thank you for your feedback.I missed to clean up m_size. I will take a look on forward_list. \$\endgroup\$ – Balaji Oct 6 '17 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.