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

(oaktree) #1

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 `T`s 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

3 Likes

[C] Dynamic Memory (Part 5.0): Make Your Own Malloc
#2

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

1 Like

#3

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 {
Data data;
};

/*
* 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
*/

/*
* the "destructor" to free a node from memory given a
* pointer to a struct _node
*/
``````

###list.h

``````typedef struct _list {
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
*/

/*
* 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);
``````
2 Likes

(oaktree) #4

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?

0 Likes

#5

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

0 Likes

(pico) #6

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.

0 Likes

(oaktree) #7

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`.

0 Likes

(pico) #8

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.

2 Likes

(oaktree) closed #9

This topic was automatically closed after 30 days. New replies are no longer allowed.

0 Likes