[3SidedSquare]

Prerequisite: basic knowledge of arrays, creating classes and functions in python, understanding of scope.

Alright, so 3 of 4 of your ram cards went and fried themselves, and you're running a half-gig of memory. You're operating systems takes up almost all of it, and you barely have any memory left to do your hacks!!!

Here, we'll look at the Linked List, a data structure to help be more efficient with memory!

1. Contiguous memory required for arrays:

What this means, is that when creating an array you need to specify a size, and that much space is blocked off the the system's memory. For example, if you had an array that could contain up to 100 objects, but possibly less, an array would make space for all 100 objects, no matter if they had be instantiated (created and assigned to the array), or not. The solution? Linked lists!

2. The linked list

Linked lists are a special data structure that allows lists to grow and shrink, using and freeing memory as needed, at the cost of random access, and the small extra cost of pointers(in most languages, python has no need for pointers!) Linked lists are built by using nodes to hold an object, and the next node in the list. The last node in the list references it's object, but instead of another node, references null (or None in python).

ListNode.py

Code:

class ListNode(): obj = None nextNode = None def __init__ (self, value = None, next = None): self.obj = value self.nextNode = next def setNext(self, next): self.nextNode = next def setValue(self, value): self.obj = value def getNext(self): return self.nextNode def getValue(self): return self.obj

Now that we have a class that can create nodes for us, let's do stuff with them!

Making a list of odd numbers:

Code:

import ListNode.ListNode startNode = ListNode(1,None) lastNode = startNode for i in range(0,10): lastNum = lastNode.getValue() nextNode = ListNode(lastNum+2,None) #Starting at 1 and adding 2 should give us only odd numbers lastNode.setNext(nextNode) lastNode = nextNode

Hooray! We now have a linked list of odd numbers! But it's rather useless if we can't read number, isn't it? Note that only the first node in the list, startNode, is kept, so we have to transverse the array to get or find an object. For this reason, we say that a linked list's get() method has a Time Efficiency of O(n), where n is the size of the list. In other words, the larger the list, the longer it'll take to get the value you want on average. (If you know you will require some values more frequently than others and don't want to transverse the whole list, look up Heaps)

Traversing a linked list:
(Assume startNode is the first node in a linked list of strings)

Code:

nextNode = startNode while(nextNode.getNext() != None): print(nextNode.getValue()) nextNode = nextNode.getNext() #Remember that the value is assigned once the right side of the = has been evaluated. In other words, nextNode.getNext() will be found before it is assigned to nextNode. This allows us to go through the list with minimal references.

That easy! But why would you use this over any other array? What actually makes it special?
The fact that it can grow and shrink, freeing and taking up memory as need be.

Adding the number 6 after 5
(Assume startNode is the first node in a linked list of integers, and that 5 exists in the list)

Code:

nextNode=startNode ##loop until nextNode references the value 5 while(nextNode.getValue() != 5): nextNode = nextNode.getNext() ##To insert a number, we need to know the nodes before and after the new node we want to put in beforeNode = nextNode afterNode = beforeNode.getNext() ##Create a new node, and set it's next to afternode newNode = ListNode(6,afterNode) ##Link it into the list by having the node referencing 5 link to the node referencing 6 beforeNode.setNex(newNode)

And there you have it, list growth! this can be done even at the beginning or at the end, only difference is when inserting at the beginning, newNode becomes the new startNode; and at the end afterNode is None

Removing gets a little trickier, as you need to keep track of the node before the value you want to delete.

Removing 8 from a linked list
(Assume startNode is the first node in a linked list of integers, and that the value 8 exists)

Code:

##Handel this special case where it is at the beginning of the list, as my code won't do it if(startNode.getValue() == 8): startNode = startNode.getNext() ##Loop until the node AFTER nextNode contains the value 8 nextNode = startNode while(nextNode.getNext().getValue() != 8): nextNode = nextNode.getNode() ##now, to remove the value, just skip over it. (if you want to be really tidy, you can delete it manually using python's [url=http://docs.python.org/3.2/tutorial/datastructures.html#the-del-statement]del[/url] keyword) afterNode = nextNode.getNext().getNext() nextNode.setNext(afterNode)

This code will correctly handle deletion if the node to be deleted is at the end. But this has been the rough and ready of linked list.

If you think you've had enough 'how do I even linked lists' for now, close out your browser and relax, have some day dreams, eat some carrots, and come back later when you're fresh. Remember that you're here on your own time for fun! Don't stress out.

If you're a rough and tumble hacker; read on!

Prerequisite for continuing from this point: Knowledge of what processes are, and some basics of multiprocessing.

Linked lists, as opposed to arrays are incredibly useful for the simple fact that they don't depend on a start and size definition; they can grow and shrink as much as they like from any point. Arrays need to do a lot of shifting whenever you add or remove a value, but not linked lists! this allows for some very interesting multi-threading operations on linked lists. (This is literally the only useful application I know of for linked lists in python)

Using a pool of 4 workers to replace any number from 10 to 20 with the number 25
(Assume startNode is the first node in a linked list of integers, and that p is a Pool of 4 workers)

Code:

#first, find the length of the list, so we can efficiently operate on it. x = 1 nextNode = startNode while(nextNode.getNext != None): x++ nextNode = nextNode.getNext() #Now that we have length n, devide up the list into sections for our workers to work on sect1=startNode sect2=sect1 for i in range(0,x/4): sect2 = sect2.getNext() sect3 = sect2 for i in range(0,x/4): sect3 = sect3.getNext() sect4 = sect3 for i in range(0,x/4): sect4 = sect4.getNext() def assign(sect): sNode=sect while(sNode hasattr getValue()): if(sNode.getValue() > 10 and sNode.getValue() < 20): sNode.setValue(25) ##Actually assign workers to do the work p.map(assign(sect1),1) p.map(assign(sect2),2) p.map(assign(sect3),3) p.map(assign(sect4),4)

I hope you enjoyed the tutorial on linked lists, this is what the basic linked list is, and how to use it. For more, please see:

doubly linked lists
circularly linked lists

Inb4 303315 is furiously trying to find holes in my tut (<3 you too)