Linked list in C++

README.md

Linked-list in C++

This is a comparison to ChunMinChang/31f11789bb859356daf05107e8fc859e, which simulates C++ classes to implement linked-list in pure C.

TODO

• Implement delete function to remove a node from the list
• Implement move function to move cursor to a specific node
• Implement search function to return one specific node

Comparison with C version

• The C version needs to call destroy explicitly, while the C++ version will automatically run deconstructor ~List() to release the memory, or use smart pointers like unique_ptr to help memory management.
  • To release Foo* n = new Foo(...), we need to use delete n instead of n->~Foo()
    • Calling a destructor releases the resources owned by the object, but it does not release the memory allocated to the object itself.
• We need to pass self pointer to the List structure for calling functions to access list's data, while we don't need to do that in C++ version because class object can get all data inside itself in its implementation.
• To allow storing different data type in the list, the C++ version use template instead of void* in the C version.
  • The void* data with size_t size is regarded as memory chunk beyond types, pointed by data with size bytes, so we can store different types data in runtime.
  • While template<typename T> let us to declare a variable with type T in compile time, so gcc/g++ can help us for debugging if there is any error.
    • function with template cannot be separated in .cpp and .h because compiler needs to see both the template definition and the specific types/whatever used to fill in the template. Please read this for more details.
• Replace NULL with nullptr
  • nullptr is always a pointer type. NULL(0) could cause ambiguity when we have functions: void f(int), void f(foo *), and we call f(NULL).

Reference

• Why can’t I separate the definition of my templates class from its declaration and put it inside a .cpp file
• How to define a template class in a .h file and implement it in a .cpp file
• Storing C++ template function definitions in a .CPP file

list.h

#ifndef LIST_H
#define LIST_H

#include <assert.h> // for assert
#include <memory>   // for std::unique_ptr

template<typename T>
class List
{
public:
  struct Node // All it's members are public by default.
  {
    Node(T aData, Node* aNext)
      : mData(aData)
      , mNext(aNext)
    {}

    ~Node() {}

    T mData;
    Node* mNext;
  };

  List();
  ~List();

  void Append(T aData);
  void Prepend(T aData);

  typedef void (*Callback)(Node* aNode);
  void Traverse(Callback aCallback);

private:
  // No need to use smart pointer in low-level data structure.
  // It's more efficient for managing memory on our own.
  Node* mCursor;
  Node* mHead;
};

// nullptr is introduced in C++11.
template<typename T>
List<T>::List()
  : mCursor(nullptr)
  , mHead(nullptr)
{
}

template<typename T>
List<T>::~List()
{
  for (mCursor = mHead ; mCursor != nullptr ;) {
    std::unique_ptr<Node> autoRelease(mCursor);
    // Update mCursor here instead of afterthought in for-loop,
    // in case mCursor is already released.
    mCursor = mCursor->mNext;
    // The memory chuck pointed by old mCursor will be destroyed
    // upon leaving the '}'.
  }
}

template<typename T>
void
List<T>::Append(T aData)
{
  Node* n = new Node(aData, nullptr);
  if (!mHead) { // the list is empty.
    assert(!mCursor);
    mHead = n;
  } else {
    assert(mCursor);
    mCursor->mNext = n;
  }
  mCursor = n;
}

template<typename T>
void
List<T>::Prepend(T aData)
{
  Node* n = new Node(aData, mHead);
  mHead = n;
  if (!mCursor) { // The list is empty before inserting value.
    mCursor = n;
  }
}

template<typename T>
void
List<T>::Traverse(Callback aCallback)
{
  for (Node* cur = mHead ; cur != nullptr ; cur = cur->mNext) {
    aCallback(cur);
  }
}

#endif // LIST_H

makefile

CXX=g++
CFLAGS=-Wall -std=c++14

TEST=test.cpp
EXECUTABLE=$(TEST:.cpp=)

all:
	$(CXX) $(CFLAGS) $(TEST) -o $(EXECUTABLE)

clean:
	rm $(EXECUTABLE)

test.cpp

#include "list.h"
#include <iostream>

template<typename T>
void Print(T aData, bool aBreakline)
{
  std::cout << aData << ((aBreakline)? "->" : "\n");
}

void PrintInt(List<int>::Node* aNode)
{
  Print(aNode->mData, aNode->mNext);
}

void PrintFloat(List<float>::Node* aNode)
{
  Print(aNode->mData, aNode->mNext);
}

int main()
{
  int dataInt[6] = { 11, 22, 33, 44, 55, 66 };
  float dataFloat[6] = { 1.1f, 2.2f, 3.3f, 4.4f, 5.5f, 6.6f };

  List<int> li;
  li.Prepend(dataInt[0]);
  li.Append(dataInt[1]);
  li.Append(dataInt[2]);
  li.Prepend(dataInt[3]);
  li.Append(dataInt[4]);
  li.Prepend(dataInt[5]);
  li.Traverse(PrintInt);

  List<float> lf;
  lf.Prepend(dataFloat[0]);
  lf.Append(dataFloat[1]);
  lf.Append(dataFloat[2]);
  lf.Prepend(dataFloat[3]);
  lf.Append(dataFloat[4]);
  lf.Prepend(dataFloat[5]);
  lf.Traverse(PrintFloat);

  return 0;
}