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 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.