Annotated edit history of
LinkedList version 6, including all changes.
View license author blame.
Rev |
Author |
# |
Line |
1 |
SamJansen |
1 |
A data structure used in programming to allow dynamic length lists allowing quick iteration, addition and subtraction from the list. Random access is not quick, however, requiring a search of the list. There are a few variants of [LinkedList]s: singly-linked lists, doubly-linked lists and circular lists (which can be either singly or doubly linked). |
|
|
2 |
|
|
|
3 |
A simple singly linked list in C++: |
|
|
4 |
|
|
|
5 |
template<class T> |
|
|
6 |
struct !LinkedListNode |
|
|
7 |
{ |
|
|
8 |
T data; |
|
|
9 |
!LinkedListNode *next; |
|
|
10 |
}; |
|
|
11 |
|
4 |
GlynWebster |
12 |
[LinkedList]s work by each node merely pointing to the next node in the list, where the last node has a NullPointer. Doubly-linked lists have a previous pointer as well, allowing bi-directional iteration. A circular list has the last node pointing back to the first node. Adding and deleting nodes aren't terribly complex but require a little thinking; you need to store temporary pointers and do a little magic. |
3 |
GlynWebster |
13 |
|
6 |
AristotlePagaltzis |
14 |
Most higher level languages have linked list constructs. For example [C++] has the [STL], [Java] has a LinkedList in its class libraries. Category:FunctionalProgrammingLanguages almost always have linked lists as built-in datatypes, the linked list is the primary datatype in [LISP]. If you are coding [C], however, you might have to write your own. |
3 |
GlynWebster |
15 |
|
|
|
16 |
''Note'': Python has a "list" datatype, but it is implemented as an array of pointers, so don't treat it like a linked list -- prepending elements to the head of a Python list one by one is not an efficent thing to do. |