Dungeon Coder

 

Links of Chainmail

Introduction to Linked Lists

It's time to start getting into the meat of things, so to speak. So, herein ye shall learn of Linked Lists, the first of many Data Structures we will explore in the dungeon.

What is a data structure, you might ask? It's a structure for data, of course! That is, data structures are like blueprints we can design and make use of when trying to store and interact with different kinds of data for different purposes. Nothing but time and experience will help you identify when to use which data structures. For now, let's get back to linked lists.

To begin covering linked lists, we are going to make more use of object oriented programming which you began to learn about in a previous lesson. Getting a bit fancier, we will actually be creating 2 classes within one piece of python code. Before I go on, take a look at the following (please don't run away in horror):

Woah. That's a lot of code! (Or, at least it seems like a lot of code if you haven't been exposed to as much code before). Let's break it down a bit.

class Node: begins the creation of our Node class. What the heck is a node? Nodes are what we use to build our linked list. They are what our linked lists are made of. Imagine a node as a link in a chain linked fence (or a link in a piece of chainmail armor). Without any nodes, we have no linked list.

def __init__(self, data, nextNode): begins the definition of the constructor (see previous lesson on object oriented programming) for our Node objects. Recall that self simply refers to the Node object calling the function. data refers to the information being stored in our Node object. nextNode is just going to keep track of the next Node in what will be a list of Nodes. Keep in mind the chainmail analogy: if none of the links are connected, then you just have a bunch of links scatterred about. Not very useful as either a chain or a piece of armor.

Let's skip on down to the linkedList class. Rather than breaking down each line, I'll describe in general what's going on. A linked list will consist of Node objects all connected together. We keep track of a headNode (the first Node in the linked list) and the tailNode (the last Node in the list). We have functions for getting the headNode, printing the entire list, and adding a Node to the list. There will be future lessons with further detail on linked lists and other data structures. For now, experiment with the above code, and try and work your way through the assignment.

Assignment:

  1. Add a line of code that prompts a user to enter data for a new node. Use that input to add a new Node to the myList object.
  2. Issue another call the printList function to make sure that your code from question 1 worked appropriately (we call this testing/debugging)?
  3. Take your code from questions 1 and 2 and nest it within a for loop that repeats 10 times. Test it. Anything unexpected happen? Experiment with cleaning up the output. Consider moving the print line outside and down below the for loop. Is that better?
  4. Consider the linkedList class. Try and write a function that removes a specified data from the linkedList object. Keep in mind that each Node in the list has a property called nextNode which needs to point to the next Node in the list. You must not cause the linkedList to become unlinked! So, your function should start like this: def remNode(self, data): Recall that each Node has a getData() function. Each Node also has a getNextNode() function as well as a setNextNode() function. You will likely need to use all 3 of those functions in order to get your remNode(self, data) function working properly.
  5. I think question 4 was enough. Take a breather.

Join the Dungeon Crawl: A place for programmers to ponder, partake, and peruse postulations pertaining to programming, politics, potions, and pizza.

If you subscribe on Patreon, you will be granted access to the Dojo, a growing collection of quality computer science classes created and actively mantained and frequented by the Dungeon Master!

Become a Patron!

Glossary

Contact: dungeon_master@dungeoncoder.com