2
\$\begingroup\$

I'm a second year CS major currently studying Data Structures, I wanted to implemented a Linked List with whatever knowledge I have at my disposal without referring much to any books or references, just a pen and paper and what I know in C++, I would be glad if someone takes a look at the code and finds potential issues, tips, logic problems and whatnot.

template <class DataType>
class dList
{
private:
  // The Node Structure.
  struct Node
  {
    DataType data;
    Node *next;
    Node *prev;
  };
  // The 'head' And 'tail' Pointers.
  Node *head, *tail;
  // Miscellaneous Variables.
  int itemsInList; // The Number Of Items In The List.
public:
  // The Default Constructor.
  dList()
  {
    head = nullptr;
    tail = nullptr;
    itemsInList = 0;
  }
  // Insertion Operations.
  void insertEnd(DataType itemToInsert);
  void insertBeginning(DataType itemToInsert);
  int insertAfterNth(DataType itemToInsert, int afterNth);
  int insertAfterSpecific(DataType itemToInsert, DataType afterData);
  // Deletion Operations.
  int deleteBeginning();
  int deleteEnd();
  int deleteNthNode(int nthNode);
  int deleteSpecificNode(DataType nodeToDelete);
  // Display Operations.
  int displayF();
  int displayB();
  // Useful Utility Operations.
  int numberOfItems();
  bool isEmpty();
  DataType searchFor(DataType searchTerm);
};

// The Insert To The End Function.
template <class DataType>
void dList<DataType>::insertEnd(DataType itemToInsert)
{
  // Creating The New Node With The Item We Want To Insert First.
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  newNode->next = nullptr; // Since We Are Adding To The End, It'll Point Nowhere.
  // Checking If The List Is Full.
  if (head == nullptr)
  {
    newNode->prev = nullptr;
    head = tail = newNode;
  }
  // Otherwise (If The List Is Not Empty).
  else
  {
    newNode->prev = tail;
    tail->next = newNode;
    tail = newNode;
  }
  itemsInList++; // Increase The Items In The List.
}

// The Insert To The Beginning Function.
template <class DataType>
void dList<DataType>::insertBeginning(DataType itemToInsert)
{
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  if (head == nullptr)
  {
    newNode->next = newNode->prev = nullptr; // Set Both Of 'newNode->next' And 'newNode->prev' To 'nullptr'
    head = tail = newNode;
  }
  else
  {
    newNode->prev = nullptr;
    head->prev = newNode;
    newNode->next = head;
    head = newNode;
  }
  itemsInList++;
}

// The Insert After Nth Node Function.
template <class DataType>
int dList<DataType>::insertAfterNth(DataType itemToInsert, int afterNth)
{
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  Node *temp1 = head;
  int counter = 1;
  while (temp1 != nullptr)
  {
    if (counter == afterNth) break;
    if (temp1->next == nullptr) return 1;
    counter++;
    temp1 = temp1->next;
  }
  // Special Case For Tail, If Inserting After The Last Node.
  if (temp1 == tail)
  {
    newNode->next = nullptr;
    temp1->next = newNode;
    newNode->prev = temp1;
    tail = newNode;
  }
  // All Other Cases.
  else
  {
    Node *temp2 = temp1->next;
    temp1->next = newNode;
    newNode->prev = temp1;
    temp2->prev = newNode;
    newNode->next = temp2;
  }
  itemsInList++;
  return 0;
}

// The Insert After Specific Data Function.
template <class DataType>
int dList<DataType>::insertAfterSpecific(DataType itemToInsert, DataType afterData)
{
  Node *newNode = new Node;
  newNode->data = itemToInsert;
  Node *temp = head;
  while (temp->data != afterData)
  {
    if (temp->next == nullptr) return 1; // Indicating That The Node Data To Insert After Was Not Found.
    temp = temp->next;
  }
  if (temp == tail)
  {
    newNode->next = nullptr;
    temp->next = newNode;
    newNode->prev = temp;
    tail = newNode;
  }
  else
  {
    Node *temp2 = temp->next;
    temp->next = newNode;
    newNode->prev = temp;
    temp->prev = newNode;
    newNode->next = temp2;
  }
  itemsInList++;
  return 0;
}

// The Delete Beginning Function.
template <class DataType>
int dList<DataType>::deleteBeginning()
{
  // Check If The List Is Empty.
  if (head == nullptr) return 1; // Indicating That The Operation Failed, Since List Is Empty.
  // Otherwise.
  if (tail == head)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    Node *temp = head;
    head = head->next;
    head->prev = nullptr;
    delete temp;
  }
  return 0;
}

// The Delete End Function.
template <class DataType>
int dList<DataType>::deleteEnd()
{
  if (head == nullptr) return 1;
  if (tail == head)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    Node *temp = tail;
    tail = tail->prev;
    tail->next = nullptr;
    delete temp;
  }
  return 0;
}

// The Delete Nth Node Function.
template <class DataType>
int dList<DataType>::deleteNthNode(int nthNode)
{
  if (head == nullptr) return 1;
  int counter = 1;
  Node *temp = head;
  while (temp != nullptr)
  {
    if (counter == nthNode) break;
    if (temp->next == nullptr) return 2;
    counter++;
    temp = temp->next;
  }
  if (head == tail)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    delete temp;
  }
  return 0;
}

// The Delete Specific Node Data Function.
template <class DataType>
int dList<DataType>::deleteSpecificNode(DataType nodeToDelete)
{
  if (head == nullptr) return 1;
  Node *temp = head;
  while (temp != nullptr)
  {
    if (temp->data == nodeToDelete) break;
    if (temp->next == nullptr) return 2;
    temp = temp->next;
  }
  if (head == tail)
  {
    delete head;
    head = tail = nullptr;
  }
  else
  {
    temp->prev->next = temp->next;
    temp->next->prev = temp->prev;
    delete temp;
  }
  return 0;
}

// The Display Forward Function.
template <class DataType>
int dList<DataType>::displayF()
{
  // Check Whether The List Is Empty.
  if (head == nullptr) return 1; // Indicating That The List Is Empty.
  // Otherwise (If List Is Not Empty).
  Node *temp = head;
  cout << "\n\n\n" << "\t" << "| ";
  while (temp != nullptr)
  {
    cout << temp->data << " | ";
    temp = temp->next;
  }
  cout << "\n\n\n";
  return 0; // Indicating That The List Was Displayed Successfully.
}

// The Display Backward Function.
template <class DataType>
int dList<DataType>::displayB()
{
  if (head == nullptr) return 1;
  Node *temp = tail;
  cout << "\n\n\n" << "\t" << "| ";
  while (temp != nullptr)
  {
    cout << temp->data << " | ";
    temp = temp->prev;
  }
  cout << "\n\n\n";
  return 0;
}

// The Number Of Items Inside The List Function.
template <class DataType>
int dList<DataType>::numberOfItems()
{
  return (itemsInList);
}

// The Is Empty Function.
template <class DataType>
bool dList<DataType>::isEmpty()
{
  if (head == nullptr) return true;
  return false;
}

// The Search For A Specific Node Function.
template <class DataType>
DataType dList<DataType>::searchFor(DataType searchTerm)
{
  if (head == nullptr) return -1; // Indicating That The List Is Empty.
  Node *temp = head;
  int counter = 1;
  while (temp != nullptr)
  {
    if (temp->data == searchTerm) break;
    if (temp->next == nullptr) return -2; // Indicating That The Item Was Not Found In The List.
    counter++;
    temp = temp->next;
  }
  return counter; // Returns The Node Number Of The Searched Item If It's Found.
}

Thanks in advance

\$\endgroup\$
5
\$\begingroup\$
  • DRY 1. You initialize node->data regardless of where you want to insert the node. Let the constructor handle it. Better yet, let the constructor create node in the known state. A useful default is to have .next = nullptr and .prev = nullptr.

  • DRY 2. Look closely at insertEnd. The very name of the function implies that tail would point newNode no matter what, and newNode->prev would point the old tail no matter what. The only difference is a role of a newNode. A suggested rewrite:

    newNode->prev = tail;
    if (head == nullptr) {
        assert(tail == nullptr);
        head = newNode;
    } else {
        assert(tail != nullptr);
        tail->next = newNode;
    }
    tail = newNode;
    

    The same applies to insertBeginning.

    As a side note, consider renaming them to append and prepend, to to be more in line with STL, push_front and push_back respectively.

  • A delete* family fails to update itemsInList.

  • searchFor is declared to return DataType, but in fact it returns a counter, which is int.

  • I am not sure I see the utility of searchFor (who would need that index anyway? - consider returning a Node * and reusing this method in insertAfterSpecific and deleteSpecific). However, a repeated test for nullptr-ness suggests a rewrite:

    while (temp != nullptr) {
        if (temp->data == searchTerm) {
            return counter;
        counter++;
    }
    return -2;
    
  • isEmpty is implemented in a frowned upon way. Consider

    return head == nullptr;
    

    As a side note, since this condition implies itemsInList == 0 it is yet another good place to assert.

\$\endgroup\$
3
\$\begingroup\$

Well, there is lots to fix, and even more to improve:

  1. Mind the rule of 3 / 5:
    Your class manages a list of node's, except it doesn't. You implemented only the default-ctor (though you really should mark it both noexcept and constexpr), forgetting copy-/move- ctor, copy-/move- assignment and dtor.

  2. Indices are only good in the interface of a data-structure which allows constant-time indexing. You should use iterators, which gives you access to the for-range-loop and all the nice algorithms.
    If you don't have the patience to implement them, at least use raw Node* for positions.

  3. As-is you cannot express one to after the last node (single-linked-lists would use one before the first node instead). Consider reducing Node to the two pointers, and using it in the definition of dList (which also contains itemsInList) and DataNode (which also contains data), which allows you to fix that.

    template <class T>
    class dList {
        struct Node { Node *next, *prev; };
        struct DataNode : Node { T data; };
        Node base{};
        std::size_t count{};
        ...
    };
    
  4. Now that you can express a pointer past the end, you can remove all the special-case-code which you needed to work around that inability.

  5. Follow the naming-conventions of the standard-library where possible. You cannot use the power of templates (and it requires loads of additional memorizing) if everyone uses their own conventions. And writing templates to abstract away such needless differences without substance is a real pain.

  6. Use aggregate-initialization when allocating a new node. Thus, there is only exactly one place in the function where an exception can be thrown, making your code exception-safe.

  7. If you want to express failure to perform the operation with a return-code, call the operations try@@ and return a bool instead of an int you only use two arbitrary values of.

\$\endgroup\$
1
\$\begingroup\$

Obey the Rule of Three/Five/Zero.

Resource management frees the client from having to worry about the lifetime of the managed object, eliminating memory leaks other problems. A resource could be any object that requires dynamic creation/deletion.

R. Martinho Fernandes defined the Rule of Zero as follows:

Classes that have custom destructors, copy/move constructors or copy/move assignment operators should deal exclusively with ownership. Other classes should not have custom destructors, copy/move constructors or copy/move assignment operators.

Consider the following code that simply copies a list and modifies that copy.

dList<int> original;
original.insertEnd(0);      // original = [0]

auto modified = original;   // modified = [0]
modified.insertEnd(1);      // modified = [0, 1]

modified.displayF();        // prints "| 0 | 1 |"
original.displayF();        // expects "| 0 |", printed "| 0 | 1 |", oops.

The implicitly defined behavior of copying just the member values isn't enough for your managed object, so you'll need to provide your own user-defined copy operations.

The chart below shows how the compiler may not implicitly provide certain operations if you declare others yourself. C++ Special Member Functions Rather than memorizing or constantly referencing the chart, the general rule is "if you have to provide any of the special member functions, then provide them all." Scott Meyers takes it a step further, recommending:

[I]nstead of expressing [The Rule of Zero] by not declaring [member functions for copying, moving and destruction] functions, [the rule is] expressed by declaring them explicitly and equally explicitly opting in to the compiler-generated implementations.


  Node *head, *tail;

Prefer the C++ declarator style. C++ puts the emphasis on types (think about references) whereas C emphasizes the syntactical structure of the code. That also leads to the guideline of declaring one name per declaration. This is minor though and you are consistent with your usage of the C-declarator style (which is what matters).

  Node* head;  // or Node * head;

  dList()
  {
    head = nullptr;
    tail = nullptr;
    itemsInList = 0;
  }

Prefer initialization to assignment in constructors. For members initialized by a constant, prefer in-class initialization to member initialization. This helps avoid repetition and maintenance issues. Your code is explicit in that the same value is expected in all constructors and you avoid use-before-set errors.

template <class DataType>
class dList
{
private:
  Node* head{nullptr};
  Node* tail{nullptr};
  int itemsInList{0};
public:
  dList() = default;

  void insertEnd(DataType itemToInsert);

For input parameters, prefer to copy cheap types by value and other types by reference-to-const. When copying is cheap, nothing is going to beat the simplicity and safety of copying. Since DataType is a templated type, it can realistically be any object type with the potential to be large in size, you can't make the assumption that it will be cheap to copy. There are more advanced optimization techniques for passing arguments, which you can look into as you learn more about move semantics.

  void insertEnd(const DataType& itemToInsert);

Package meaningful operations as carefully named functions. Code becomes more readable, more likely to be reused, and be easier to test. Your insertAfterXXXX functions essentially search (by value or index) then insert (after node).

Return the correct types. C++ has the bool for returning true or false. searchFor() attempts to cast an int to whatever DataType is, which could fail. If you need to return to the callee the state, consider an enumeration or one of the error reporting strategies listed below.

Check to make sure your preconditions are not violated. Should the default behavior for passing an out-of-range index into insertAfterNth() (either too large or negative), result in a new node being appended to the end?

template <class DataType>
bool dList<DataType>::insertAfterNth(const DataType& new_value, 
                                    int nth_index)
{
  auto* nth_node = find_by_index(nth_index);
  return !insert_after_node(nth_node, new_node);
}

template <class DataType>
bool dList<DataType>::insertAfterSpecific(const DataType& new_value, 
                                         const DataType& search_value)
{
  auto* nth_node = find_by_value(search_value);
  return insert_after_node(nth_node, new_value);
}

For a more modern exercise, use std::unique_ptr instead of raw pointers. Watch Leak-Freedom in C++... By Default.


// The Search For A Specific Node Function.
template <class DataType>
DataType dList<DataType>::searchFor(DataType searchTerm)
{
  if (head == nullptr) return -1; // Indicating That The List Is Empty.
  Node *temp = head;
  int counter = 1;
  while (temp != nullptr)
  {
    if (temp->data == searchTerm) break;
    if (temp->next == nullptr) return -2; // Indicating That The Item Was Not Found In The List.
    counter++;
    temp = temp->next;
  }
  return counter; // Returns The Node Number Of The Searched Item If It's Found.
}

Don't add redundant == or != to conditions. Avoid the verbosity and reduce the opportunities for mistakes.

Don't say in comments what can be clearly stated in code. Compilers do not read comments. Comments are less precise than code. Comments aren't updated as consistently as code. Consider using an actual error-handling mechanism for those situations that require them. In this example, not finding an element in either an empty list or a populated list should return the same value. Returning one past the end is out the standard library does it. In your case, returning a union type (std::optional, std::variant, std::expected, or the boost:: variants) may be better.


template <class DataType>
int dList<DataType>::numberOfItems()
{
  return (itemsInList);
}

Keep code simple. C++14 adds a fringe case in which parentheses around a return value is evaluated as an expression. In this case, the expression evaluates just fine. In the world of auto-deduction, things could explode.

\$\endgroup\$
  • \$\begingroup\$ Node doesn't have an invariant. So why the ctor? \$\endgroup\$ – Deduplicator Mar 22 '18 at 1:38
  • \$\begingroup\$ Your advice on using aggregate initialization is actually better. Purged the ctor remark. \$\endgroup\$ – Snowhawk Mar 22 '18 at 1:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.