Python linked list: Cats in boxes
Hello again! In anticipation of the start of the Python Developer course , we have prepared for you a small authorial material on linked lists in Python.
A LinkedList or linked list is a data structure. A linked list provides the ability to create a bidirectional queue from any elements. Each element of such a list is considered a node. In fact, a node has its value, as well as two links to the previous and subsequent nodes. That is, the list is “linked” by nodes that help move up or down the list. Because of these structural features, you can organize a stack, queue, or double queue from a linked list.
Let's visualize dry definitions. Now we have cats that are sitting in boxes. And on each box it says what it is in order and what it should stand for.
What we will do with a linked list:
In fact, there are much more options for working with them, but we will dwell on the implementation of these basic steps. Having understood by what principle they are built, you yourself can easily implement your own methods.
You'll have to start by creating two classes:
In general, we have a node that has some value inside - a cat, and a link to the next node. That is, in the Box class, respectively, there is a cat and a link to the next box. Like any list, the coherent also has a beginning, namely head. Since there is nothing there initially, the starting element is set to None.
Let's start with a simple one. To check if there is any particular cat in one of the boxes located in series, you need to cycle through the entire list, checking the existing value with the values of the element in the list.
First you need to create a new box, and already put a new cat in it. After that, it is necessary to check, starting from the beginning of the linked list, if there is a link to the next one in the current node and if there is one, then go to it, otherwise the node is the last one, so you need to create a link to the next node and put the same new box in it, which we created.
By the index catIndex we want to get a box node, but since the nodes are not provided with such an index, we need to come up with some kind of replacement, namely a variable that will act as an index. This variable is boxIndex. We go through the entire list and check the "serial number" of the node, and if it matches the desired index, we give the result.
Here we consider the removal of an element not by index, but by value, in order to introduce at least some variety.
The search starts from the head of the list, that is, from the first box in a row, and continues until the boxes end, that is, until the headcat becomes None. We check if the value stored in the current node matches the one we want to delete. If not, then we just move on. However, if it matches, then we delete it and “re-link” the links, that is, we delete the N-th box, while the N-1 box now refers to the N + 1 box.
That's all, thanks for reading the material! In fact, the LinkedList structure is not complicated, and it is important to understand how it works from the inside. Of course, in Python it could have been implemented in lambda expressions, it would have taken up much less space, but here I aimed to explain its structure, and the principle of its operation in Python as detailed as possible, rather than chasing optimization.
The source code can be found here .
Python is a very convenient and multifaceted language, but by default it does not have such a data structure as a linked list or LinkedList. Today I will share my best practices on this topic and talk a bit about what this data structure is. This article will be of interest to those who first come across the topic of linked lists and want to understand how they work from an algorithmic point of view.
What is a LinkedList?
A LinkedList or linked list is a data structure. A linked list provides the ability to create a bidirectional queue from any elements. Each element of such a list is considered a node. In fact, a node has its value, as well as two links to the previous and subsequent nodes. That is, the list is “linked” by nodes that help move up or down the list. Because of these structural features, you can organize a stack, queue, or double queue from a linked list.
Let's visualize dry definitions. Now we have cats that are sitting in boxes. And on each box it says what it is in order and what it should stand for.
What we will do with a linked list:
- Check whether this or that element is contained in it;
- Add nodes to the end;
- Get the value of a node by index;
- Delete nodes.
In fact, there are much more options for working with them, but we will dwell on the implementation of these basic steps. Having understood by what principle they are built, you yourself can easily implement your own methods.
You'll have to start by creating two classes:
class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None
In general, we have a node that has some value inside - a cat, and a link to the next node. That is, in the Box class, respectively, there is a cat and a link to the next box. Like any list, the coherent also has a beginning, namely head. Since there is nothing there initially, the starting element is set to None.
Is the item in the list
Let's start with a simple one. To check if there is any particular cat in one of the boxes located in series, you need to cycle through the entire list, checking the existing value with the values of the element in the list.
def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False
Add node to end of list
First you need to create a new box, and already put a new cat in it. After that, it is necessary to check, starting from the beginning of the linked list, if there is a link to the next one in the current node and if there is one, then go to it, otherwise the node is the last one, so you need to create a link to the next node and put the same new box in it, which we created.
def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox
Get a node by index
By the index catIndex we want to get a box node, but since the nodes are not provided with such an index, we need to come up with some kind of replacement, namely a variable that will act as an index. This variable is boxIndex. We go through the entire list and check the "serial number" of the node, and if it matches the desired index, we give the result.
def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex <= catIndex: if boxIndex == catIndex: return lastbox.cat boxIndex = boxIndex + 1 lastbox = lastbox.nextcat
Delete node
Here we consider the removal of an element not by index, but by value, in order to introduce at least some variety.
The search starts from the head of the list, that is, from the first box in a row, and continues until the boxes end, that is, until the headcat becomes None. We check if the value stored in the current node matches the one we want to delete. If not, then we just move on. However, if it matches, then we delete it and “re-link” the links, that is, we delete the N-th box, while the N-1 box now refers to the N + 1 box.
def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None
That's all, thanks for reading the material! In fact, the LinkedList structure is not complicated, and it is important to understand how it works from the inside. Of course, in Python it could have been implemented in lambda expressions, it would have taken up much less space, but here I aimed to explain its structure, and the principle of its operation in Python as detailed as possible, rather than chasing optimization.
The source code can be found here .
All Articles