Data Structures (Part 1.1): Linked List [Class Destructors]

[oaktree]

Hey 0x00sec community!

This one will be short. Today, I’m going to show you the destructors I have implemented for my List and node classes.

---

A Recap of the Header Files

node.h:

template <class T>
class node {
  private:
	T data;
	
  public:

  	node<T>* next;
	
	// class constructor
	node(T _data = 0, node<T>* ptr = nullptr)
		: data(_data), next(ptr) {}
	
	~node();

	// other methods
};

(lol, so using Java syntax highlighting makes comments work, but C++ highlighting doesn’t. “Note to self…”)

---

list.h:

template <class T>
class List {
  private:
	  node<T>* root;
	  size_t len;

  public:

  	List()
  		: root(nullptr), len(0) {}

  	~List();

  	// other methods

---

Destructors

list destructor

template <class T>
List<T>::~List() {
        if (root != nullptr) //EDIT: only delete root if it isn't a nullptr
	        delete root; // root is a node<T>*,
	// whose destructor deletes whatever the node points to
}

---

node destructor

template <class T>
node<T>::~node() {
	if (next != nullptr) {
		delete next;
	}
}

---

Why It Works

In my design for linked lists, we never interact with nodes outside of the List class, meaning we never deal with naked nodes, nor do we deal with pointers to nodes on our own.

Every node is handled by a List.

In some main(), I can make a new list like so:

List<int> mylist;

Currently, I have only made a constructor for List that takes no parameters.

If I want to add a node to mylist, I call mylist.append(<some data>). Note: I have yet to show you append(...), but it does exist and it does work.

List's append() takes care of acquiring resources for a new node. Now, remember that List has two data members: node<T>* root and size_t len. The one relevant to us now is node<T>* root. That is a pointer. How do we work with pointers in C++? new and delete.

So, when I append(...) to mylist, I essentially do new node<T>.

When mylist goes out of scope, ~List() gets called. All it does is delete root. But, in deleting root, which is a node<T>*, we call ~node(). In ~node(), we delete next (remember that next is a node<T>*) IF next is not a nullptr (NULL in C). When we delete next, we call the destructor for next. Wait, what destructor is that? ~node()!

BOOM. So, using implicit recursion, the entire linked list, consisting of node<T>*s gets deallocated responsibly.

Keep linking those lists guys,
oaktree

[Cromical]

Thanks for the post mate! Keep 'em coming! Excited to see what you’ll have for “Part 1.2”

[dtm]

C implementation:

node.c

void freeNode(link n) {
    free(n);
}

list.c

void freeList(List l) {
    while (l->first != NULL) {
        // grab a hold of the first node so it is reachable
        link temp = l->first;
        // shift first's next node to become new first
        l->first = l->first->next;
        // free old first
        free(temp);
    }
    // free list itself
    free(l);
}

P.S. I also noticed the syntax highlighting disappearing after the first code block.

[Donnette (Donnette Pinkerton)]

You are seriously smart, oaktree!

Thanks for inviting me here! I love it!