Sunday 15 March 2015

Linking Nodes: Wrapping up your one child tree

The instant I read about Linked Lists, what I thought about was the impossible bet explained in Minute Physics. The solution to that puzzle involved a linked list of the sorts and, while the video is not about linked lists, it does outline one of the benefits of this data structure: it is an organized way to sequentially traverse through information.

What is a Linked List Node (LLNode)?
It is an object that has two pieces of information:

  • value = object held by the node (e.g. a number)
  • next = reference to the next node (i.e. another LLNode)

Does this ring any bells? Well, of course: it is identical to the attributes from our original Tree, with next instead of children (and next being the next node, while children was a list of nodes).

What is a wrapper?
Nodes could go on forever, or perhaps not. When we want to use a particular section of a chain, we use a wrapper to define the beginning and the end of it, as well as the size. The attributes of a wrapper are the following:

  • size = size of chain
  • start = starting node
  • end = ending node
As the name implies, the wrapper wraps itself around the nodes.

The Challenge

The appearance of a wrapper changes everything! While we used to use recursion in a kind of happy-go-lucky way, we now need to keep in mind that recursive code has to deal with the nodes inside the wrapper. Hence, it will have a different nature since changes will need to be made on the nodes and/or the wrapper. These are some examples and what they change:

  • Delete Node: Nodes + Wrapper
  • Change Node Value: Nodes
  • Add Node: Nodes + Wrapper
  • Shorten Wrapper: Wrapper
Let's keep these in mind for the next post, where we will explore how recursive code can change the wrapper and the nodes.

5 comments:

  1. Replies
    1. I loved the solution they found to better the odds :D Linking nodes FTW

      Delete
  2. If I can quibble over an extremely minor point in an otherwise good post, the "wrapper" of a linked list doesn't actually need to store information about the last node. So long as it stores the first node, and every node contains a pointer to the next one, all you need to do is keep going over them until you find the one which has no pointer to another node (IE the tail).

    I think one of the interesting things about linked lists is how they can be instantiated in such a bare-bones way. Unlike lists, you can chose whether or not your linkedlist will be able to contain, for example, information about the index of a node or link in the linked list, or whether it will be able to count how many elements are inside it, etc.

    All of these properties, while undoubtedly useful for solving lots of problems, may be unnecessary for solving other problems. So the ability to save time by never implementing them may be a large bonus.

    Oh, and great observation about how linked lists are like trees with a branching factor of one!

    ReplyDelete
    Replies
    1. Thanks! Continuing on your point about not really needing a last node, it does seem redundant to have an attribute for size AND a last node. Even if your last node does link to another node, the first node and the size is all you need. You raised a very good observation there, and it makes you really think about how simple linking nodes are in comparison to other objects. From a computational point of view, I am looking forward to seeing the usefulness that these offer, particularly after being reminded class after class about how lists waste resources when working on a big scale.

      Delete
  3. Pretty cool bet! Wouldn't have thought comp sci logic goes beyond pesky 165.

    ReplyDelete