Linked List
- Tags
- comp-sci
Is a data structure where each node (element) contains a link to the next node and the [see page 9, list] structure only keeps a pointer to the head of the list. You can use a doubly linked linked-list by having each element store a pointer to its parent element as well.
Table 1:
see page 9, [Operations] on linked-lists.
| Method | Description |
|---|---|
x.key | The value of the node x. |
x.next | A pointer to the next node from x. |
x.prev | A pointer to the previous node from x (in a doubly linked-list). |
L.head | A pointer to the node at the head of the linked list L. |
You can [see page 10, search] through a linked list in linear time by simply inspecting each element one after the other. The advantage of linked lists over regular arrays is that insertion and removal are constant time operations. You can add an element to any position in a linked list so long as you have the node at that position.