Need help understanding nodes and linkedlists

Question

I'm learning about nodes and linked queues (are these pretty much the same as linked lists?) and I'm not fully understanding what a node is. Is it a node an element in a list that refers to the next element? I'm learning from this site http://openbookproject.net/thinkcs/python/english3e/queues.html and it uses this code:

class Queue:
    def __init__(self):
        self.length = 0
        self.head = None

    def is_empty(self):
        return self.length == 0

    def insert(self, cargo):
        node = Node(cargo)
        if self.head is None:
            # If list is empty the new node goes first
            self.head = node
        else:
            # Find the last node in the list
            last = self.head
            while last.next:
                last = last.next
            # Append the new node
            last.next = node
        self.length += 1

    def remove(self):
        cargo = self.head.cargo
        self.head = self.head.next
        self.length -= 1
        return cargo

I really need understanding what node and cargo are, thanks in advance

Answer 1

It helps to visualize linked lists as "box and pointer" diagram.

The pairs of boxes stuck together are what your program calls nodes. The two boxes represent the two parts of the node. One box holds (points to) the "cargo" the other holds the "next". A node has two parts, a "cargo" and a "next".

The "next" member of a node either points to another node or to nothing ("NIL" in the image above). The "cargo", well, is the cargo.

In the list above the node containing 42 in it's cargo is the head of the list. Your queue only needs to hold onto the head. Using the "next" member of the nodes the queue can "walk" the list to get to each element.

I'm assuming somewhere there is a Node class defined something like this:

class Node:
    def __init__(self, cargo):
        self.cargo = cargo
        self.next  = None

To understand how your queue works let's build the queue in the image.

When you first create your queue object the queue head pointer points to None to represent an empty queue.

q = Queue()

To add the first item to the queue insert the 42

q.insert(42)

The insert function creates a node containing 42, and inserts that node into the head position since there is nothing else there yet. It also increments the length from 1 to 0.

To add the second item to the queue insert the 69.

q.insert(69)

The insert function creates a node containing 69. Then it "walks" the linked list until it reaches the node with None in it's next member. Then it changes that nodes next member to point to the new node. Insert also increments the queue length.

To add the 613 it repeats the process used to add the 69. The linked list is longer, but the process is the same.

q.insert(613)

At this point the linked list representing your queue is the list shown in the picture.

To retrieve the first item from the queue:

x = q.remove()

The remove function looks at the cargo of the head node. It contains 42. This value is stored to be returned after the queue does it's book keeping. The node containing the 42 needs to be removed from the front of the queue and, the next node needs to moved to the head. To do this the remove function gets the next node from the current head node and sticks that in the queues head position. The old head node is now an orphan, no one is pointing to it, so the garbage collector will make sure it is cleaned up. The new linked list is the last two nodes in the image. The cargo is then returned to the caller and stored in x.

To retrieve the next item from the queue:

y = q.remove()

The same process is repeated except the cargo of the head node is 69, and the next node is the node whos cargo is 613. After this function call y contains 69 and the linked list in the queue only contains the node containing 613.

---

Addendum: Walking a linked list:

The while loop in Node.insert() "walks" the linked list. In this function "last" is a bad name for the variable. It should just be node, because during the while loop it points to each node in the linked list for one iteration of the while loop. (Node.next should be Node.tail, but that's an argument for another time.)

Before the loop starts the variable last is assigned the head node. last = self.head. (In most cases the head node is not the last node, hence the bad variable name) The while loop condition "last.next" checks whether the node currently in the variable last (most of the time not the last node) is actually the last node. The actual last node will have None in it's last member, and None as a Boolean is false. If a node does not have None in it's last member it's last member points to the next node. So to "step" to the next node in the linked list, the body of the while loop assigns last to the node in the current last's next.

Expanding the example above: Consider the step where we inserted the 613. Before we insert the 613 the linked list is two nodes. The head node (pointed to by self.head of the queue object) contains 42 in it's cargo member, and contains the second link in it's next member. The second link contains 69 in it's cargo and None in it's next member. The second link is the last link of the list.

To walk the list the variable next is assigned to the link containing 42 in it's cargo. (At this point the variable last does not point to the last link in the list.) The while loop condition looks at the next member of the link in the variable last (the first link), to determine if it contains None. It does not, so the body of the while loop executes. The body of the while loop takes the node in the last member of the node contained in the variable last (the next member of the first node), and puts that node in the variable named last. The body of the loop ends. At this point the while loop evaluates the loop condition. The node currently in the variable last is actually the last node (remember, we are in the process of appending the node containing 613, so the list only has two nodes) so last.next is None. The while loop terminates and, at this point, the variable last actually contains the last node.

Hopefully, you can see how this would work for longer lists, but it would take a lot more words to describe.

---

To sum it all up, (relating queues, linked lists, heads, nodes, cargos, and nexts): Your queue points to the head of a linked list, made up of nodes containing cargos and nexts. The queue inserts new items at the end of the linked list, and removes items from the head of the linked list. Hopefully that all makes sense.

Answer 2

In this particualr example, a node contains information about its neighbor (next) in the tree so that it can traverse through the list. It also contains a reference to the cargo which is the actual data being stored in the node.

Another important variable to understand here is head, which is always the first (front) node in the tree. Since this is a queue (specifically a FIFO queue), the remove (typically called pop in other implementations) function returns the cargo of the head as well as removing it from the queue and setting the new head of the queue to the old head's next.

Answer 3

A "node" is an item in the linked list -- it's what's being linked. The "head" is the first node in the lined chain. "cargo" is the data that's contained within the node. A "queue" is a form of list that has a beginning and an end and proceeds in order, first-in-first out (as oppose to a stack, which is last-in-first-out, or a loop.