[アルゴリズム]リンクリスト

For those of us who use Python as a main computing language, we tend to take the benefits of the List function for granted. It is so easy to use and utilize the List function, and it is also very intuitive. However, there is so much more to the List function than you can imagine. In today’s post, I will go through a concept called the ‘Linked List’, which is essentially an anatomical version of python List function.
What do we need in lists? In other words, what can we do with lists? We can append, get the size of the list, view how the list looks like, delete, replace, search (search using the item’s name or its index), and insert. In order to implement these functions through the concept of ‘Linked List’, we obviously need to understand how ‘Linked List’ works. In the ‘Linked List’, we only know the very first item. Yes, you heard it right. Only the first item. We can only know what lies beyond by using that first item and following what is linked to it, and following its link, and following its link again until we find amongst those links what we were looking for (Somewhat similar to how humans try to predict the future). In order to do this, we need two information per item: the data (the name of the item) and the infamous link. The link points to the location the second item is at, therefore completing the concept of a Linked List. Let’s look at the visual example.
Let’s say there is a list: [‘Lyla’, ‘Python’, ‘Tom’, ‘Sally’]. Figure 1 is the visualization of this list, made from what we can infer from the theory of the Linked List:
Figure 1. A hopeful visual representation of the linked list
But in reality, this will look something more like this:
Figure 2. An actual visual representation of the linked list
The link part of the item doesn’t contain an arrow, obviously. It contains a coordinate number of the next link’s location. It looks something like this:

<__main__.Node object at 0x03D750E8>

Where do you think the link of the last item (here it’s Sally) will point to? The answer is nowhere. In computing language, the link part of the last item will contain the information None. So if you try to retrieve the coordinate number of the link pointing nowhere, you will get an error message like this:

AttributeError: 'NoneType' object has no attribute 'link'

Hmm… So, an item contains a data and link… Sounds familiar? Yes, this sounds like a Node in a network! That is why we will conceptualize the item by utilizing the ‘Node’ concept from a network. Here is how:

class Node:
    def __init__(self, data, link):
        self.data = data
        self.link = link

Each ‘Node’ now has two information: a data and link.
Let’s move on and make another class called the LinkedList. Here, I will implement the functions of the list I talked about earlier (append, insert, get the size of the list, view how the list looks like, delete, search (search using the item’s name or its index). These functions will be the methods of class LinkedList. Therefore, the skeleton of the class LinkedList will look something like this:

class LinkedList:
    def __init__(self,):
 #variables

    def push(self, data):
 #add a new item in the front
    def size(self):
 #return the length of the list
    def display(self): #view how the list looks like
    def delete1(self): #delete the first one
    def search_data(self, data):
 #see if the data is there and return its position            
    def search_pos(self, position):
 #see if the position is there are return its data
    def insert(self, pos, data):
 #insert a new item at a specific location
    def delete2(self, pos_or_data):
 #delete an item at a specific location
    def replace(self, pos, data): #replace an item with a new one at a specific location
 

The class LinkedList will contain one variable called the head that is pointing Nowhere. When I let the head to point somewhere that contains some kind of an information, the list is finally linked. The code will look like this:

class LinkedList:
    def __init__(self,):
 #variables
        self.head = None

I explained earlier that Linked Lists makes the list by letting each item(node) to point the next one in line. To add an item in the first index of an empty list, all you have to do is let the head point your new item. But if we have a list with more than one item, the head should point at your new item and your item should point at the item that used to be the first one.
Figure 3. How adding an item to a Linked List works
That is why I am going to make a method that checks whether the list is empty or not. If the head is pointing at nowhere, it indicated no item(node) is linked, which means it is an empty list:

    def is_empty(self):
        if self.head == None:
            return True
        return False

Let’s use the is_empty(self) function to make the push() function explained earlier. The item(node) we are adding should become an object of the class Node named temp:

    def push(self, data):
        if self.is_empty():
            temp = Node(data, None)
            self.head = temp
        else:
            temp = Node(data, None)
            temp.link = self.head
            self.head = temp

If we can add, we should also need to be able to delete. To delete the first item on the list, all you got to do is for the head to point the item in the second index.

    def delete1(self): #delete the first one
        if self.is_empty():
            print('Empty list')
        else:
            x = self.head.data
            self.head = self.head.link
            print(x, 'is deleted')

(I will get to inserting and deleting an item(node) in a specified position later!)
The size of the Linked List essentially means how many links are there that does not point to None. We will make a variable that travel these links, starting from the head, and counts how many links it has travelled. This variable can travel the links by redefining itself as the ‘link of the link’ every time it reaches the next link. So its definition will constantly change: head à head’s link à head’s link’s link à head’s link’s link à … When he reaches the node where its link points to None, he stops counting and returns the number, which is the length (size) of the list:

    def size(self):
        c = self.head
        cnt = 0
        while c != None:
            cnt += 1
            c = c.link
        return cnt

Since we learned how to add a new item to the list, delete an item, and return the size of the list, let’s display what we have. This will use almost identical logic as we did for the size() function, but instead of counting its travelling distance, it will print the data on the way. Since I also want to print the arrows (‘->’), but not for the last one, I will use if-else statement to denote when to add the arrow and when not to add the arrow, that is, when the link of its current location is pointing at the next item(node) and none, respectively:

    def display(self): #view how the list looks like
        c = self.head        
        if self.is_empty():
            print("Empty list")
        else:
            while c != None:
                if c.link != None:
                    print(c.data, end = '->')
                else:
                    print(c.data)
                c = c.link

Looking for a certain item(node) and finding its location is easy when you are dealing with a small list, because you can display() it and count them. When the list gets longer, however, we need an extra function to do that job for us. The search function can work in two ways: I look for a specific item(node) or I look for its position. Either way, if the item(node) is in the list, it will return the position or data, respectively. Both will include a function is_empty() to denote the case when the list is empty. Both also has a variable that will travel through the link: for search_data() it will check whether the item we are looking for is identical to the data of the node the variable is situated at. If so, it will return the number that has been counting the distance it has travelled, and return True. For search_pos(), it will do the same but return the data of the node the variable is situated at when the number that has been counting the distance it has travelled has matched the position we are looking for, and return True. For both functions, if the item(node) we are looking for is not in the list, it will print a statement and return False. Hence, these functions can both be used to return the result and Boolean result:

    def search_data(self, data):
        c = self.head
        if self.is_empty():
            print('Empty list')
        else:
            cnt = 0
            while c != None:
                if c.data == data:
                    print(cnt)
                    return cnt, True
                    break
                cnt +=1
                c = c.link
            print('Not in the list')
            return False

    def search_pos(self, position):
        c = self.head
        if self.is_empty():
                print('Empty list')
        else:
            cnt = 0
            while c != None:
                if cnt == position:
                    print(c.data)
                    return c.data, True
                    break
                cnt += 1
                c = c.link
            print('Not in the list')
            return False

I promised to show how to insert and delete an item in a specified location, so here it goes. In order to do this for insert, we need two arguments: where and what to insert. For delete, just one: what or where to delete. As you know, Linked List only works in a way where the item’s link is pointing at the location where the next item is situated. Therefore, to insert an item(node), the link of the item before the item in discussion, which I will denote pnode, should point to the location where the item in discussion is at, and the link of the item in discussion should point to the location of the item that was next to pnode. Similarly, to delete an item, the link of pnode should simply point at the location of the item next to the item in discussion.
Figure 4. A visual representation of how insertion and deletion works in a Linked List
It will be useful to make a function that shows what a specific item(node) is from the perspective from the head. I will call this getNode(), and this will return the location where a specific item is at.

    def getNode(self, num):
        c = self.head
        while c != None:
            if num == 0:
                break
            c = c.link
            num -= 1
        return c

The insert() method takes two arguments, position(pos) and data(data). First, create a new Node object with the given argument, which I will denote temp. If you want to insert an item(node) at the very start of the Linked List, it will execute the push() method. If not, getNode() function that takes pos-1 as an argument will return the location where the item before the item in discussion is located at, which I denoted as pnode. It is extremely important that the item(node) you will insert will point at the item at the position pos before assigning the link of the pnode with the position of the item(node) in discussion, because if it is done backwards, the position of the item at pos+1 is lost.
The link of the pnode will point to where temp is at, and the link of temp will point to the item(node) that is at pos+1 of the Linked List.

    def insert(self, pos, data):
        temp = Node(data, None)
        if pos == 0:
            self.push(data)
        elif pos < self.size():
            pnode = self.getNode(pos-1)
            temp.link = pnode.link
            pnode.link = temp
        else:
            print('List is too short')

The delete() method takes one argument that could be either string value or integer value(pos_or_data). If it is an integer value, getNode() method that takes pos_or_data-1 will be executed to be assigned to the variable pnode, and the link of pnode will point to the location where the item that used to be next to the ‘deleted’ item was. If the argument is 0, self.head will directly point at the link of its link. If the argument is a string value, search_data() method is executed to return its index value first, and afterwards will operate identically as the case with integer.

    def delete2(self, pos_or_data):
        if type(pos_or_data) == str:
            pos = self.search_data(pos_or_data)[0]
            if pos == 0:
                self.head = self.head.link
            else:
                pnode = self.getNode(pos-1)
                pnode.link = pnode.link.link
        elif pos_or_data < self.size():
            if pos_or_data == 0:
                self.head = self.head.link
            else:
                pnode = self.getNode(pos_or_data-1)
                pnode.link = pnode.link.link
        else:
            print('List is too short')

Lastly, how should we replace a data in a certain location? This will be similar to insert() method, but will include small modification. This method still takes two arguments, position(pos) and data(data). First, create a new Node object with the given argument, which I will denote temp. If you want to replace the first item(node), it will execute the push() method, which will insert the item at position 0. Then, delete2() function will be executed to delete the item(node) situated at position 1. If the position is not a zero, it will execute the identical algorithm to insert, but the inserted item will now point at the item located at pos + 1.

    def replace(self, pos, data):
            temp = Node(data, None)
            if pos == 0:
                self.push(data)
                self.delete2(1)

            elif pos < self.size():
                pnode = self.getNode(pos-1)
                temp.link = self.getNode(pos+1)
                pnode.link = temp
            else:
                print('List is too short')

Linked List is finally finished! Let’s play around with it 😊

ml = LinkedList()

print('What is in my list right now?:')
ml.display() #Empty list
print()
print("Let's add some names: ")
ml.push('lyla')
ml.push('giwon')
ml.push('sonia')
ml.push('carson')
ml.push('susi')
ml.display() #susi->carson->sonia->giwon->lyla
print()
print("Let's search some names and positions! 0, lyla, kiwon, 5 respectively : ")
ml.search_pos(0) # susi
ml.search_data('sonia') #2
ml.search_data('kiwon') #Not in the List
ml.search_pos(5) #Not in the list
print()
print("Let's delete the first item in the list: ")
ml.delete1() # susi is deleted
ml.display() # carson->sonia->giwon->lyla
print()
print("Let's delete lyla and whoever is in the 0th position from the list")
ml.delete2('lyla') #3
ml.delete2(0) #0
ml.display() #sonia -> giwon
print()
print("Let's insert susi at position 1 and replace index 2 with carson: ")
ml.insert(1, 'susi')
ml.replace(2, 'carson')
ml.display() #sonia -> susi -> carson

The result is:

What is in my list right now?:
Empty list

Let's add some names: 
susi->carson->sonia->giwon->lyla

Let's search some names and positions! 0, lyla, kiwon, 5 respectively : 
susi
2
Not in the list
Not in the list

Let's delete the first item in the list: 
susi is deleted
carson->sonia->giwon->lyla

Let's delete lyla and whoever is in the 0th position from the list
3
sonia->giwon

Let's insert susi at position 1 and replace index 2 with carson: 
sonia->susi->carson
>>>