1. Introduction
Data structures and algorithms in the context of computer science are essential because of the key role that these concepts play in programming. Most software programs will use these notions to manipulate data, and therefore, the study of these methods is crucial for the proper understanding of code.
To learn about and implement these ideas, we can choose between many different programming languages, each of which is capable of performing the necessary tasks. In order to select the tools best suited for our needs, this tutorial will discuss the main ideas behind data structures, and their adaptations in today’s most popular programming languages.
2. Overview
A data structure is a way of organizing computer memory space in a mathematical fashion, enabling efficient access to the values therein. As such, data structures and algorithms are often discussed together because the creation and deletion of structures are carefully guided through algorithms. Most often, we’ll implement methods to achieve the most basic tasks for a data structure. These tasks can be grouped into the following categories:
- Insertion
- Deletion
- Searching for an element
In order to complete these tasks, we manage memory using pointers and dynamic memory allocation. In object-oriented programming, the management of memory is often done at a class level through our constructors and destructors. This general idea of freeing used space when we don’t need it is called garbage collection. Ideally, we try to form efficient algorithms that only change what’s necessary to complete the tasks.
Finally, the efficacy of these operations can be calculated through time and space complexity analysis.
3. Simply Linked List
It’s important to note that different programming languages have their own advantages and disadvantages. We’ll demonstrate this by implementing a straightforward, 3-item simply linked list in the most common programming languages, detailing the differences between them. This linked list is a basic data structure composed of data nodes. Each node will hold some information and a pointer to the next node.
We’ll only cover the construction of the structure, leaving out the many other functions necessary for a full implementation, such as insertion, deletion, checking list size, and so on.
Our structure will look like this:
3.1. C
We’ll begin with a strongly typed language that requires all variable and object types to be explicitly specified. It’s often used in embedded systems, databases, and driver development.
First, we can construct our main function. Because C isn’t object-oriented, we can use structures instead of defining a class. Here’s an example of what our Node and LinkedList structures could look like:
typedef struct node_t {
char * data;
struct node_t * next;
} node;
typedef struct SLinkedList {
node* head;
} linkedList;
Then we can link the nodes together:
node1->next = node2;
Using these instructions, we can make a LinkedList structure, and have its head point to our first node.
C requires us to be explicit with our coding, which makes it the perfect language for someone that wants to learn how to implement things from scratch. However, it’s not object-oriented, and it requires us to manually de-allocate the memory we used up later in the code; there’s no garbage collection here.** Also note that we have to include libraries to work with strings, amongst other things.
3.2. C++
This language is widely used as part of many operating systems, as well as in the making of efficient video games and machine learning tools. It can be seen as the object-oriented version of C. This means that C++ will support abstraction, polymorphism, encapsulation, and inheritance.
As a result, we can replace structures with classes. The advantage here is that we can place the functions that allocate and de-allocate memory space in our constructors and destructors. These are the functions that generate and destroy our objects, and they’re called automatically.
Furthermore, we can define public and private specifiers because C++ supports encapsulation. This brings us added access control to our variables. Our node class can look like:
class Node {
public:
char * data;
Node* next;
Node() {
data = NULL;
next = NULL;
}
};
And the LinkedList:
class SLinkedList {
public:
SLinkedList(Node* firstnode) {
head = firstnode;
}
private:
Node* head;
};
Note that the head pointer is only accessible through the constructor of the SLinkedList class, as it’s placed under private. In contrast, because our implementation doesn’t encapsulate the next variable of the Node, corrupting the linked list is possible by assigning it some other value.
We can see that the syntax of C++ is relatively similar to C, with some exceptions. C++ remains strongly typed, but it’s more concise than C.
3.3. Java
Java is a high-level language based on C++. It’s used in all the same fields as C++, and we can also see that the syntax is very similar. Note that this language includes a lot more functions from the start, without needing to include any external libraries.
In this language, we also don’t have to include any libraries to work with strings. We can begin our code by defining a class, just like in C++. This time, we can nest the Node class inside the LinkedList:
class SLinkedList {
class Node {
string data;
Node next;
Node(string d) {
data = d;
}
}
SLinkedList (Node start) {
head = start;
}
}
We can implement the constructor directly in the class. If we make classes for our nodes and include the text in their constructor function, we can define them using the new keyword. Then we can use this again when implementing the linked list:
SLinkedList mylist = new SLinkedList(new Node ("First"));
Most importantly, the C-based languages discussed (C, C++, Java) are ideal for the cross-platform implementation of software, as most machines already come with the required runtimes in the OS.
3.4. Python
Python is another high-level language that’s used in a wide variety of fields, from machine learning to web applications. There’s no need to specify that we’re using a pointer for this and a string for that, as the language is loosely typed.
Just like with Java, we don’t need to import anything to work with strings.
First, we can define a class:
class Node:
def __init__(self, dataval = None):
self.dataval = dataval
self.nextval = None
Notably, the indentations here matter very much and define the order of functions.
We can also define default values directly in our constructor. We can then make Nodes and SLinkedList just by calling the constructors:
Node1 = Node("First")
List1 = SLinkedList(Node1)
Finally, we can link the nodes by assigning the next node to the object:
Node1.nextval = Node2
This makes for simple, concise syntax that’s easy to understand. It’s important to note that the semicolons are not necessary after each instruction, and the indentations on the code matter, as they define the structure of functions and loops. We also don’t need to use any commands to manage memory space, as the constructors and destructors allocate and free the memory. Python does most of the garbage collecting for us.
This means that python is a language that does a lot to simplify our tasks, which comes with advantages and disadvantages.
For example, arrays in Python are automatically treated as linked lists. As such, we can add any different data types to the same array; it’ll just hold a pointer to a different memory space. This isn’t the case in C, as arrays can only hold elements of the same type in continuous memory space. That makes it a lot faster to access the memory in C, at the cost of not being able to insert different data types:
This means that if we don’t want to define any classes, or implement this linked list from scratch, the exact equivalent can be summed up to a single line:
Positions = ["First","Second","Third"]
In addition, we can use all sorts of different predefined methods to acquire the length of the array, append to it, count, remove or insert.
3.5. Javascript
Javascript is a programming language that’s mostly used in web development. Attention to detail matters a little bit more with this language than with Python.
We can begin by declaring our classes:
class Node {
constructor(text) {
this.position = text;
this.next = null;
}
}
class LinkedList {
constructor(head = null) {
this.head = head
}
}
We can see in the code snippet above that we have to use brackets to define functions, as well as semi-colons to conclude each instruction to the machine. Constructors are defined rather explicitly, as opposed to in other languages. We also don’t have to define position or next before the constructor.
Just like Java, the syntax for making nodes is similar to C++:
let node1 = new Node("First");
Finally, we can also see that we’re managing memory spaces with the new keyword, just like in C++, which wasn’t the case in Python.
4. Summary
As previously stated, all of these languages are able to perform basic data structure tasks. In order to pick the best language, it’s helpful to discuss what and how exactly we plan to program. Now that we have a broader understanding of what each language looks like, we can more accurately make a decision.
If what we care about is:
- A very precise, low-level understanding of each basic process, or we want to work with embedded systems: C
- Machine learning: C++ or Python
- Web: Javascript or Python
- Game development: C++, Java, or Python
- Something easy to write, with few gotchas and lots of garbage collection: Python
To summarize, an arbitrary table below compares the different languages:
Language
Conciseness
Garbage Collection
Gotchas
Memory Control
Understanding of Underlying Processes
C
None at All
None
Many
Full
Complete
C++
None
Through Classes
Many
Full
Thorough
Java
Somewhat
Through Classes
Some
Almost Full
Thorough
Python
Very
Complete
Very Few
Little
Partial
JavaScript
Somewhat
Through Classes
Few
Almost Full
Thorough
5. Conclusion
There are many other languages we didn’t mention in this article, like Go and Swift, for instance. However, many of these are syntactically similar to C or C++. Therefore, knowing the languages above can give us a head start on learning the other ones. The most important thing is simply to start somewhere!