Double Linked List Part 2

The importance of the links.

A double link makes a few things possible. As a foundation, the two links are also foundational to binary trees, and many sorted data structures. In a binary tree the links can be used to insert data into a structure on a ‘more than’ and ‘less than’ value system.

Think of travelling on a set of streets. The linked list is linear, and there are no shortcuts. As the search for the address goes on, you can only travel down the short one way streets in one direction, so even if that address is at the very end of the path, the whole path has to be traveled. Also related, bubble sort.

To sort this kind of structure, one must touch every node on every iteration to change it’s location. Slowest of sorts, in contrast something with double links can be sorted with a quick sort, where nodes when you have them, can be swapped in place because the neighbors and it’s addresses for it’s neighbors are contained in the node.

In a binary tree, the data is arranged so that one can cut across the paths, or in better words, the paths are set up in such a way that travelling down the roads directly to a location is not bound by one way travel. The car can go left, if the value is known to be on the left side of town, or right if it’s on the right side of town. Once in that position, we can once again say, do we need to go east or west? And so on, until the location is reached, bypassing all unrelated paths to the address.

The delete/remove method

The value of double linked lists lies in the ability to look ahead, and look back. In a single linked list, you can move among the nodes, but once you’ve gotten to your location, there is no going back. This is where the double links are helpful. Removing, replacing and swapping out values becomes easy. The addresses of the neighbors are known by each node. Delete/remove is a great example.

-- start code block --

 def remove(self, obj):
        head = self.begin
        while head:
            if head.value == obj:
                result = head.value
                self.detach_node(head)
                self._length -= 1
                return result
                #testing return result
                break
            head = head.next


    def detach_node(self, node):
             ### node ###   [  <---1  , 2DATA , 3--->  ]  
             ### list ###
       # [(/), 1DATA , ((2--->))][**<---1**, 2DATA** 3--->**](([<----2)))), 3DATA, (/)]
             ### after detach ###
       # [(/), 1DATA , 3--->][<---1 3DATA, (/)]
        if node.prev == None and node.next == None:
            self.begin = None
            self.end = None

        elif node.prev == None and node.next != None:
            # node is a begin node:
            #[(/) node ---next-->][<----new---->]
            newnode = node.next
            if newnode.next != None:
                # newnode is not the end node
                self.begin = newnode
                self.begin.prev = None
            else:
                # newnode is the end node
                # two items on list
                self.begin = newnode
                self.end = None
                self.begin.prev = None


        elif node.next == None and node.prev != None:
            # node is an end node:
            # [<---new ---node ---->][<--new--- node  (/)]

            newend = node.prev
            if newend.prev == None:
                ## newend is the begin node
                ## two items on list
                self.end = None
                self.begin.next = None
            else:
                ## node is end node
                ## more then two on list
                self.end = newend
                self.end.next = None

        else:
            ## item in the middle of list.
            ## not begin or end node

            prevlink = node.prev # <---1
            #[(**<---1**), 2DATA,  3-->]

            nextlink = node.next # ---> 3
            #[(<---1, 2DATA, (**3--->**))]

            #node.prev.next = 2--->
            #[(/), 1DATA, ((**2--->**))]
            # nextlink == ----> 3
            node.prev.next = nextlink

            #node.next.prev = <----2
            # [**<---2**, DATA3, (/)]
            # prevlink == <-----1
            node.next.prev = prevlink

-- end code block --

The middle of the list is the important bit. When I’ve passed the node in to be removed, it has both neighbors’ information. We can tell the neighbors to this node, this is your new neighbor’s address, and remove the one that originally occupied their links.

The node to be deleted holds the previous nodes address, and the next nodes address, and as such we can access them, and tell them that the node in question is gone, and squeeze them together by changing the links that originally pointed to that removed node, to each other instead.

Wikipedia: Double Linked List

The pop method

With a single linked list, depending on which direction the list is built, only the next neighbor is known, and to retrieve the neighbors a sorting algorithm would have to find that neighbor before a removal can be done. Once again think bubble sort in comparison to Quick Sort.

The detach node in the code can be reused in different operations, think pop() where the last item is removed and returned, or shift(), where the first item is removed and returned.

Here’s the code for those two operations.

--start code block--

 def shift(self):

        head = self.begin
        # end and begin node never occupy the same space
        # If a list size is one, we will still be retrieving the first node

        if head != None:
            temp = head.value
            self.detach_node(head)
            self._length -= 1 
            return temp 
        else:
            message = "This is an empty list"
            print(message)
            return None

#--------- pop() --------------# 

def pop(self):
        lastnode = self.end 
        if lastnode != None:
            temp = self.end.value
            self.detach_node(self.end)
            # in detach_node, the length is not changed
            self._length -= 1
            return temp

        elif self.end == None and self.begin != None:
            temp = self.begin.value 
            self.detach_node(self.begin)
            self._length -= 1 
            return temp
        else:

            message = "The list has no last value: empty list."
            print(message)
            return None

--end code block--

As I wrote this draft, I realized I had never created a pop() for my Double Linked List and set out to make it. Through the typos, and the pytests, I cleaned it up rather quickly and was able to add it as intended to the post. Some would say knowing these lists are unnecessary in entry-level jobs, and as someone who is horrid at memorization, I agree that memorizing them is not efficient. An understanding of the structures is valuable however. In the bigger picture, as your code evolves, understanding them will help you troubleshoot problems in other structures, and algorithm challenges as they present themselves.

I’m going to include the graphical method I used to print off the nodes of the DLL, so if you want to tool around with making one, you can have a way to print off what is going on in your lists in the shell/CLI/Command prompt.

Bonus code, Graphical

Example use:

With the DLL.py as the file that the Double linked list and node object reside. If you’ve named yours something else, don’t forget to change the DLL => yourfilename. Remember, the file must be in the same folder as the one you create below, or you’ll get
Import errors.

--code somefilename.py--

from DLL import * 

# create list
mytrees = DLList()
mytrees.push('pine')
mytrees.push('maple')
mytrees.push('palm')
mytrees.push('redwood')
mytrees.push('baobab')

mytrees.graphical()

--endcode--

As always, take it, break it, learn and may the spam be ever in your flavor.

-- Graphical method--

 def graphical(self):
        ##  graphical uses the prev, to go through the list.
        ##  so it's like an invariant check..................
        ## None = (/)
        ## [ link = node in list ]
        ## OBJ =  (data count)DATA?
        ##   [  prev  2 , third data,  next none ]
        ## so, [ <---2 , (3) DATA ,  (/)  ]
        length = self._length
        node = self.begin
        if self.begin == None:
            print(" EMPTY ")
        elif self.begin != None and self.end == None:
            print("\n\n")
            # [(/), (0) DATA, (/)]
            print(f"{node.value}=")
            print(f"[(/), (0) DATA, (/)]")
        else:
            node = self.end
            #I only modify length to keep track
            if node:
                print("\n\n")
            while node:

                # example, length is 3
                if node.next == None and node.prev != None:
                    # [ <--2 , (3)DATA , (/) ]
                    print(f"\t\t{node.value}=")
                    print(f"\t [<-- {length -1}, ({length})DATA , (/) ]")
                elif node.next != None and node.prev != None:
                    # [ <--1, (2)DATA , 3-->]
                    print(f"\t\t{node.value}=")
                    print(f"\t [<-- {length -2}, ({length-1})DATA, {length}-->]")
                    length -= 1
                else:
                    # [ (/), (1)DATA , 2-->]
                    print(f"\t\t{node.value}=")
                    print(f"\t [ (/), (1)DATA, 2--> ]")
                node = node.prev
                print("\n")

end notes

Part 3 will be discussing the swapping nodes and inserting them.
It may be a little bit, I need to re-write my swap methods. They are a bit spaghetti at the moment.

Blog

Double Linked List Part 2

Nellie

The importance of the links.

The delete/remove method

The pop method

Bonus code, Graphical

end notes

Join Our Newsletter. No Spam, Only the good stuff.

Related