What now? Stacked Queues?, Tree Stacks?, what more can you think of? LinkedLists of course!
"LinkedLists?" I hear you ask. Well, let's start at the basics.
A LinkedList is like a chain. It is a linear network of "links" which connect together to form a large structure.
Each "link" is only aware of other links in it's immediate vicinity.
So, a LinkedList consists of nodes (links). Each node contains 2-3 parameters. 2-3, that's it? Yep, that's it.
This is because each node is a very simple object, and what differentiates it from other ADTs, it the connection protocol of the nodes.
So each nodes holds some data object. This can be anything. The remaining (1-2) parameters store the information of the other adjacent nodes to which our current node is "linked" to.
So we have a collection of nodes, all these nodes are connected to each other like links in a chain. Lets say I want to access the data at node 5. I can not just immediate jumped to node 5, I need to start at the tip of the chain (head) and work my way down, 1 node at a time, till I reach node 5. Because of their recursive design, LinkedLists are very versatile and relative easy to code. LinkedLists can easily be edited. By changing the head or changing a pointer inside of one of the nodes, a LL can be shortened or extended.
To be honest, I really don't see how LinkedLists are useful yet. They seem to be in some grey zone between a Stack and a Tree. They can work as a dynamic stack which can pop elements from both ends and remove elements from the middle, but really, it really isn't a stack if you can do all that stuff.
They also resemble very constricted trees. SURE, each node can be though of as having a child, but then again, what's the use of a tree with only one hierarchy of elements which form a long chain of elements.
The only thing I see good in LinkedLists is that they can be used to greatly reduce operation complexity of a Queue, when it comes to things such as enqueue.
But that comes back to the fundamental optimization problem. You are either burdening your memory to makes things quicker, or you can do a lot of processing to go light on the memory. So it is not some amazing game changing design, just a different way of structuring your problem (queue efficiency).
The only thing I see good in LinkedLists is that they can be used to greatly reduce operation complexity of a Queue, when it comes to things such as enqueue.
But that comes back to the fundamental optimization problem. You are either burdening your memory to makes things quicker, or you can do a lot of processing to go light on the memory. So it is not some amazing game changing design, just a different way of structuring your problem (queue efficiency).
No comments:
Post a Comment