Moving it all around.

When I wrote the original swap() method it took many twists and turns to get unwanted results. When I approached it this time, I wrote bits and pieces and tested it as I went.

All the current code for the Double Linked List, it’s pytest file, and a simple starter file to play with methods are in this GitHub repo:

Python DLL on github

What are the reasons you would want to move the nodes around?

• To sort
• To remove/add data
• To get/set new data

When looking at sorting methods in many languages, the language needs to be able to change the position of the data in the list. A simpler way than the swap method below, is to just swap the data from one node to the other and not mess with the pointers/links.

The problem with doing that is there may be more than one data set in the node. Now given the node in this particular case has just one data, self.value, if in the future the node was modified or replaced to hold more than just one piece of data, we want to preserve all the items in the node. Even though it’s more complex to swap the entire node, we now have a Linked List that is written for future use.

I stumble around every time I have to play with the next and previous. Especially with this swap. The code, and then some explanation.

swap code:

 def swap(self, index1, index2):
        node1 = self.get_node(index1)
        node2 = self.get_node(index2)
        print(f"size = {self._length}")
        if node1 != None and node2 != None:
            #print(f"node1 = {node1.value} , node2 = {node2.value}")
            self.swap_helper(node1, node2)
        else: 
            message = "One or both of the index's are an index Error. \n Could not swap"
            print(message)
            raise IndexError

    def swap_helper(self, node1, node2):

        #[or NONE spam -- n1-->][<---spam---node1--eggs--->][<--n1--eggs or NONE]
        #[or NONE bags -- n2-->][<---bags---node2---nots-->]<---n2--nots or NONE]
        ### make sure they are not next to each other ###
        temp1_next = node1.next 
        temp1_prev = node1.prev 
        temp2_next = node2.next 
        temp2_prev = node2.prev
        #print(node1, node2)

        #[<--  node1 --->]*CHECK*[<--- node2 -->]
        neighbor = False
        if node1.next != node2 and node1.prev != node2:
            node2.next = temp1_next
            node2.prev = temp1_prev
        else:
            neighbor = True

        if node2.next != node1 and node2.prev != node1:
            node1.next = temp2_next
            node1.prev = temp2_prev
        else:
            neighbor = True

        if neighbor:
           if node1.next == node2:
               node1.next = temp2_next 
               node1.prev = node2 
               node2.prev = temp1_prev 
               node2.next = node1 
           elif node1.prev == node2:
               node1.prev = temp2_prev 
               node1.next = node2 
               node2.next = temp1_next 
               node2.prev = node1 


        #print(node2, node1)
        # swap the nieghbors pointers               
        # neighbors 
        #[<-- prev neighbor -->][<-- node1 -->][<-- next neighbor -->]
        #[<-- prev neighbor -->][<-- node2 -->][<-- next neighbor -->]

        if temp1_next != None:
            if temp1_next != node2:
                temp1_next.prev = node2

        else:
            self.end = node2

        if temp1_prev != None:
            if temp1_prev != node2:
                temp1_prev.next = node2 
        else:
            self.begin = node2

        if temp2_next != None:
            if temp2_next != node1:
                temp2_next.prev = node1
        else:
            self.end = node1

        if temp2_prev != None:
            if temp2_prev != node1:
                temp2_prev.next = node1
        else:
            self.begin = node1

Explanation swap()

In the code, the swap_helper is doing the work of reassigning our addresses, (the links/pointers).

There are a few things that need to be considered when moving them:
1) Are one, or both nodes the lists tail and head? (self.begin, self.end)
2) Are these nodes pointing back at each other? (neighbors)
3) Do the nodes exist? (IndexError)

The code addresses each of these statements in steps.

An IndexError is handled in the top method swap(), if it is not a valid index, we want to let the user know right away, and stop the process there.

The tail and head, begin/end are important, because if we just swap out the links, the attributes that the list uses, self.begin and self.end will not change. Our list is now broken. Whenever we use either of these to retrieve something from the list the self.begin and self.end were not set to the new node values that point the the appropriate next and previous nodes.

The reason the neighboring links are important, is regular swapping of these nodes will cause a recursion. They will point back to themselves and cause a loop.

By addressing each of these issues, we can also assure that any two valid index’s can be given by the user, in any order, and they will be swapped effectively.

They can use swap(0, 10) and get the same results for swap(10, 0). Whatever the preferred order of the user is in entering the index they want swapped, it will work either way.

This is accomplished because each node is treated as it can be anywhere on the list. The first index could be an end node, or it could be a begin node. We check both things for each node to ensure the swap is done correctly.

The bit I’ll admit I always stumble over is the last piece. Swapping out the neighbor pointers.

Each node has two neighbors, (If it is not an end, or a begin).

#[<-- prev DATA A -->][<-- node1 -->][<-- next DATA C  -->]
#[<-- prev DATA H -->][<-- node2 -->][<-- next DATA J  -->]

Since we’re swapping the entire node out to preserve all pieces of data, We will need to change the pointers/links that inhabit the neighbors.

#[NEXT points to node1 address -->][NODE 1][<--PREV points to node1 address]
#[NEXT points to node2 address -->][NODE 2][<-- PREV points to node2 address]

When we change these nodes, the address in the prev and next nodes needs to point to the proper address for the swapped node.

Since this is a doubly linked list, we can access those nodes to change the pointers just by having the nodes that are being swapped.

The next of node 1, is node1.next. The previous of node1 is node1.prev.

Once we have those, we can just change them to point at the swapped node, node2.

The problem when these two nodes are next to each other is that the nodes already point at each other, and not some other item in the list.

Instead of the next/prev of its neighbors pointing to a different unique location, they will point at the nodes we are swapping.

#[<-- DATA A -->][<-- node1 -->][<-- node2 -->][<-- DATA D -->]

So instead of those temps being something like
PREV neighborA = node1.prev
NEXT neighborB = node1.next
PREV neighborC = node2.prev
NEXT neighborD = node2.next

That neighbor B is actually node2.
So if we were to swap the links without accounting for that our new arrangement would look like this:

# [DATA A -->][<--  node2   <--next  ]       [--prev -->  node1 --> ] [DATA D]

Our list is now broken, because once it hits either of these nodes, it circles back on itself, and as I found out, it could loop indefinitely.

In order to fix this, we check both nodes to make sure they don’t point at each other in either the NEXT or the PREV. If they do, we need to manually set those links to point at the other node, because otherwise, the nodes will point back at themselves.

How could swap be used?
Python already has a neat trick built into it. You can swap assignment values like so:

somelist[A], somelist[B] = somelist[B], somelist[A]

Think sorters, higher structures that may access the lists like hash tables, and if there are more reasons I’d love for you to drop them in the comments.

Insert

The insert can be used when a user wants to add new data into a specific location in the list.

This currently does not attach already existing nodes.
May add this feature.

This too does a bit of manipulation with the neighbor links, as we are pulling two nodes apart to add the new node in. If the item is going at the beginning of the list, I have written a ‘prefix’ function to handle that, and if it’s going at the end it will be a push(). We cover those grounds even though a user should be pushing instead of inserting in the instance of wanting it at the end of the list, but humans are human. Let’s leave wiggle room for whatever they can throw at this list.

When I wrote this, I had to look up C implementations to see how they changed the links, because I couldn’t wrap my brain around setting the links in the correct order without overwriting links and destroying the order before it could be changed.

Example:

#            NODE B
# PREV = NODEA,  DATA,  NEXT=NODEC
#
#            NODE C 
# PREV = NODEB, DATA, NEXT=NODED

If I change that NEXT pointer in NODEB before I have that address stored, like so:
NODEB.NEXT = Newly_Inserted_Node

When I go to get the next node, NODEC, to assign it’s previous pointer, I’m actually going to get
Newly_Inserted_Node instead of NODEC

The Insert

    def insert(self, obj, index):

        head = self.begin
        tail = self.end
        length = self._length
        # check if they are just pushing.
        if index == length:           
            self.push(obj)

        # check if they are prefixing        
        elif index == 0:            
            self.prefix(obj)

        # check if they are indexing out of range:
        elif index > length:
            # to bypass pytest error, import pytest and in your test use:
            # with pytest.raises(IndexError):
            #    mylist.insert('obj', 99)
            # where obj is the item being pushed, and 99 the index out of range
            print(f"the length of this list is: {length}")
            raise IndexError



        # [(/), (a)DATA, (b)-->]  [else]  [<---(a)DATA, (/)]
        else:

            head = self.begin
            count = 0
            while head:

                if index == count:
                   self.attach_node(head, obj)
                   self._length += 1
                   break
                else:
                    head = head.next
                    count += 1




    def attach_node(self, node, obj):
        #                    newnode
        ### node ### [<---a ,   x   , b--->] ### node ###

        #    old previous ((a))      index node being replaced((b))
        #  [ ~~ ,  a , --->]   ((x))    [<----, b , ~~ ]

        newnode = DLLNode(None , obj, None)
        #1 [<---a--,  x ,  (/)] set prev of newnode
        newnode.prev = node.prev
        #2 [<---a--, x , --b--->] set next of newnode
        newnode.next = node
        #3 [~~  ,  a  , ---x-->] set next of previous node to newnode
        node.prev.next = newnode
        #4 [<--x---, b , ~~ ] set previous of the index, given node to newnode
        node.prev = newnode
        # doing (3 and 4)   out of order will break your list.

explanation insert()

When working with data structures, inserting an item at an index can be a useful tool. Think once again of sorting, or higher order structures that may access a linked list as storage.

A table for instance where you want a new data row to go in between two other pieces.

The table will need to be able to insert the row, or an existing row, moving the data around to the users specifications.

Data Structures are a foundational piece of software engineering and data manipulation. I hope these articles have helped in some way to broaden the understanding of what happens under the hood of your code.

Drop comments, as always, feel free to take it, break it and have fun.

Internet Explorer compatible
Level 2 of LinkedList game