Changes

Jump to: navigation, search

Linked List

3,150 bytes added, 04:55, 4 December 2009
no edit summary
This page is aimed at giving a conceptual overview of the uses and design elements of a linked list. Linked lists are flexible and powerful and can prove to be very useful tools in the arsenal of a UI designer or implementer. Therefore, having a linked list handy would make most hackers' lives a whole lot better :)<br/><br/>
With that being said, '''read on!'''
== DESIGN: What is a "linked List"? ==
 
https://cs.senecac.on.ca/~btp300/pages/content/linkl.html (On Stacks and Queues and a General Linked List)
 
 
http://en.wikipedia.org/wiki/Linked_list (A more in depth definition)
 
[http://www.ljubomirgorscak.com/recordings/fardad_linked_list_intro.mp3] (Intro to linked lists)
== ADVANTAGES: So, what's so good about a linked list? ==
== DISADVANTAGES: Well there has to be a downside! ==
-incomplete-Most of a linked list's disadvantages consist of speed issues.== DESIGN: What = Seek By Traversal ===As opposed to a sequential array, linked lists cannot be randomly accessed. In computer science, we say that a linked list has access time O(n) where n is the number of elements in the array. This means that in the worst case, every single element of a "linked List"? list must be accessed before the desired index is reached. Compare this with the constant access time of a sequential array. In computer science, we say that an array has access time O(1); this means that regardless of which index you desire, the access time for it will ''always'' be the same. The reason for this is that arrays are laid out sequentially in memory which allows computers to access any one of their elements nearly instantaneously. The reason for this is that modern computers are built with the ability to read any given memory address at the exact same speed as reading any other memory address; we call this type of memory Random Access Memory.=== Overhead ===-incomplete-As well, linked lists can be a headache to implement (although very simple implementations can take no time at all!). As opposed to an array which is very simple to work with (trivial access, trivial assignment, trivial allocation, etc...), linked lists require a lot of processor overhead. This is mainly due to the fact that linked lists must be dynamically allocated piecemeal (ie one element at a time) and the fact that dynamic memory allocation itself isn't very fast. On top of that, every single action that a linked list can perform must be programmed. Linked lists are absolutely not trivial/native which is why they are '''always''' slower than sequential arrays when it comes to access, search, initialization/destruction, etc. 
== ELEMENTS: Nodes are everything! ==
-incomplete-
-incomplete-
== FLEXIBILITY: Data Types ==
=== Custom Functionality ===Linked lists tend to be very flexible. Due to the fact that they are written by hand, all kinds of functionality can be added to them. Things such as:* Automatic allocation/de-incompleteallocation of objects* Custom linking structures* Custom index operators* Unique search algorithms* Automatic update of external code* Automatic logging/reporting* Future extensibility* Etc, etc, etc... === Data Type Hiding ===Since the implementation of a linked list is custom, the programmer may very well implement the list in any way that they may see fit. This effectively hides the data being stored from the watchful eyes of the calling program. As well, the actual location of the data is effectively random (as opposed to being sequential) which means that the data is that much harder to find. This adds a simple layer of security that arrays simply do not afford. == AUTHOR: Word From The Author ==Thanks for reading my page, now go and write yourself up a neat little linked list (well... page isn't quite complete enough for that just yet >.>) :)<br/><br/>-this message brought to you by: '''northWind87'''
Acfunktron
1
edit
Retrieved from "https://wiki.cdot.senecapolytechnic.ca/wiki/Special:MobileDiff/30828...31217"

Navigation menu