Implementing a Linked List
Some programming languages, such as Java, come with linked lists built into the language. Many languages don’t, but it’s fairly simple to implement them on our own.
Let’s create our own linked list using Python. We’ll use two classes to implement this: Node and LinkedList. Let’s create the Node class first:
| | class Node: |
| | |
| | def __init__(self, data): |
| | self.data = data |
| | self.next_node = None |
The Node class has two attributes: data contains the node’s primary value (for example, the string "a"), while next_node contains the link to the next node in the list. We can use this class as follows:
| | node_1 = Node("once") |
| | node_2 = Node("upon") |
| | node_3 = Node("a") |
| | node_4 = Node("time") |
| | |
| | node_1.next_node = node_2 |
| | node_2.next_node = node_3 |
| | node_3.next_node = node_4 |
With this code, we’ve created a list of four nodes that serve as a list containing the strings "once", "upon", "a", and "time".
Note that in our implementation, the next_node refers to another Node instance rather than an actual memory address number. The effect, however, is the same—the nodes are likely dispersed throughout the computer’s memory, and yet we can use the nodes’ links to string the list together.
Going forward, then, we’re simply going to discuss each link as pointing to another node rather than to a specific memory address. Accordingly, we’re going to use simplified diagrams to depict linked lists, such as this one:
Each node in this diagram consists of two cells. The first cell contains the node’s data, and the second cell points to the next node.
This reflects our implementation of the Node class. In it, the data method returns the node’s data, while the next_node method returns the next node in the list. In this context, the next_node method serves as the node’s link.
While we’ve been able to create this linked list with the Node class alone, we still need an easy way to tell our program where the linked list begins. To do this, we’ll create a LinkedList class in addition to our previous Node class. Here’s the LinkedList class in its basic form:
| | import node |
| | |
| | |
| | class LinkedList: |
| | |
| | def __init__(self, first_node=None): |
| | self.first_node = first_node |
Note that we import node at the beginning of our code, since we placed the Node class in a separate file from this LinkedList class.
At this point, all a LinkedList instance does is keep track of the first node of the list.
Previously we created a chain of nodes containing node_1, node_2, node_3, and node_4. We can now use our LinkedList class to reference this list by writing the following code:
| | list = LinkedList(node_1) |
This list variable now acts as a handle on the linked list, as it’s an instance of LinkedList that has access to the list’s first node.
An important point emerges: when dealing with a linked list, we have immediate access only to its head. This is going to have serious ramifications, as we’ll see shortly.
At first glance, though, linked lists and arrays are similar—they’re both just lists of stuff. When we dig into the analysis, though, we’ll see some dramatic differences in these two data structures’ performances! Let’s jump into the four classic operations: reading, searching, insertion, and deletion.
