Data Structures (Part 1.0): Linked List [Class Implementations]

[oaktree]

Hello 0x00sec!

Welcome to the maiden article of my series on Data Structures. Today, I’ll be talking about Linked Lists.

What is a Linked List?

Since, you can all read Wikipedia, I don’t really have to go into much detail. But, a Linked List is a datastructure with the following characteristics:

• A root node, which points to any succeeding nodes. It can point to one node, and in turn the node to which it points may point to yet another node (and so on); or, it can point to no nodes at all.
• An O(n) search
• An O(n) delete, which deletes the node at a certain index.
• An O(n) insert function that puts a new node at a certain index.
• An O(n) insert function that puts a new node at the __beginning__, subordinating the root node`.

Quick Vocab

1. A node is a member of the linked list. A node holds one piece of data (e.g. int, double, etc.) and a pointer to another node, typically the next node.

---

Beginning the Implementation

I’ll be writing C++ code for this series. I’ll be making use of generic programming and object-oriented programming. node and list will be classes.

Class Implementations

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();

        T& d(); // data accessor

        void d(T _data); // data setter
};

Let’s go through this more-or-less line-by-line.

template <class T> means that we declare a type T to serve as a fill-in-the-blank for the future. Later on, we’ll do something like node<int> or node<char>. All the Ts will be changed to the specified type.

We declare a type and give it one private attribute: data, which is some type T.

Then there is a class constructor. The particular syntax may look somewhat cryptic. We have a member function node(...) which takes two parameters, _data, and ptr. Both parameters have reasonable default values. _data is the information you want stored in the particular node. ptr is the node to which you want this node to point.

~node() is what is called a class destructor. When a node goes out of scope in a program, ~node() is called to clean up any resources.

Note: All of the functions from ~node() down are implemented in another file, node.cpp.

d() is a member function that will allow a programmer to access a node’s data. Similarly, d(T _data) is the corresponding writer function, which allows a programmer to change the value of attribute data for a certain node.

list.h

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

      public:

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

          ~List();

          node<T>* search(const T& q);

          node<T>* insert(T val, const size_t& idx);

          T del(const size_t& idx);

          size_t size();
    };

Okay… so something weird is happening with that syntax highlighting.

List is the class that will serve as the interface for our linked list. It has two private attributes: root is a pointer to the root node in the list; len is the length of the list (this is optional). Note: size_t is like an int but it’s architecture dependent.

List() is the constructor for the class. It takes no parameters and just sets root to be a nullptr, a pointer which points nowhere. It also, logically, sets the length len of the list to zero.

~List() is the destructor. If you have not yet noticed, ~ denotes a class’s destructor. Again, from the destructor down, all of the member functions are implemented in another file (list.cpp), which I will show you in Part 1.1.

search(...), insert(...), and del(...) are the functions I mentioned earlier; size() is a function that will return the value of len, telling is how long our list is.

---

Conclusion

I did not want to make this too long, so I will be dividing Linked List up into several parts, this one being Part 1.0. Stay tuned for the implementations of search(), insert(), and del().

See ya next time, 0x00’ers,
oaktree

[Sea]

Great post! I just recently learned C# and am glad a lot of the knowledge transfers over.

[dtm]

C implementation because I’ve got nothing better to do.

node.h

/*
 * replace int to whatever suits your needs
 * since C does not provide generic types
 */
typedef int Data;
typedef struct _node *link;
typedef struct _node {
    Data data;
    link next;
};

/*
 * the "constructor" to create a new node with a value d
 * initializes link next member to NULL
 * returns a pointer to a struct _node, null if an error
 */
link newNode(Data d);

/*
 * the "destructor" to free a node from memory given a 
 * pointer to a struct _node
 */
void freeNode(link n);

###list.h

typedef struct _list {
    link first;
    size_t size;
} *List;

/*
 * the "constructor" to create a new list with size 0
 * initializes link first member to NULL
 * returns a pointer to a struct _list, null if an error
 */
List newList();

/*
 * the "destructor" to free a list from memory given a 
 * pointer to a struct _list
 */
void freeList(List l);

/*
 * searches for a node in List l with value d
 * returns a pointer to a struct _node
 */
link search(List l, Data d);

/*
 * instantiates and inserts a node into List l
 * with a value d into position pos
 */
void insert(List l, Data d, size_t pos);

/*
 * removes a node in position pos in List l
 */
void deleteNode(List l, size_t pos);

[oaktree]

Nice work, @dtm! It’d be cool if you could get those destructors to run when a List goes out of scope, but that’s a C++ thing, more or less. Correct?

[Cromical]

Thanks for the post! Beautiful code you and @dtm got there!

[0x00pf (pico)]

C++ does it with automatic variables but not with dynamically allocated objects, static variables,… @dtm redefines types as pointers what suggested that everything will be dynamically allocated. In those cases you need to use something like a smart pointer. Smart pointers are nowadays part of C++, so yes ‘the language still supports that’, but with a minor help from the programmer.

In C, if you really want to have something like that, you can add a Garbage Collector to your program.

[oaktree]

The destructors you’ll see in the next post of this series (1.1) are implemented such that resource allocation is responsible without smart pointers. @0x00pf

Believe me: If I knew there were memory leaks, I wouldn’t post the code… And I did check with valgrind.

[0x00pf (pico)]

Please note that I said something like a smart pointer. Just to be clear, what I said is that, for each new you have to run a delete. You can use some trick to fire the execution of delete but you have to call it. For automatic variables you do not have to, the compiler generates that code for you.

I’m looking forward to read 1.1. I’m now curious about what you have done.