-
Notifications
You must be signed in to change notification settings - Fork 16
/
linked_list.theory.txt
142 lines (118 loc) · 10.3 KB
/
linked_list.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
LINKED_LIST
/=+===============================+=\
/ : : \
)==: GENERAL :==(
\ :_______________________________: /
\=+===============================+=/
[SINGLY] LINKED LIST ==> #Graph where nodes always point to 1 other node ("link")
#First node is "head" or "address|pointer|handle"
#Last node is "tail"
#Used to implement lists, i.e. same operations.
#Time complexity:
# - length(), access(), search(): O(n)
# - insert(), delete(), slice(): O(1) after a O(n) search
#Pros:
# - O(1) insert|delete after a O(n) search
# - persistent data structure
# - "tail-sharing": re-using last nodes, including sentinel nodes
# - recursive data structure (providing sentinel nodes are used)
# - faster memory allocation: does not have to be contiguous and is more frequent
#Cons:
# - O(n) access|search
# - not ordered (but can manually sort)
# - links takes space
TAIL NODE ==> #Can either:
# - have no link or have a link to a sentinel node ("open|linear")
# - no link: takes less space
# - sentinel node:
# - faster search iteration (can test searched value and check sentinel node at once)
# - recursive data structure
# - link to head ("circular linked list")
# - removes persistence and recursion
#A reference to tail node can be kept in memory, for O(1) append operations.
NODE VALUE ==> #Can either:
# - be inlined ("internal storage"):
# - better space complexity
# - better time complexity for access
# - better locality of reference
# - easier memory allocation
# - be accessed through a pointer ("external storage"):
# - allow using any data structure for the value
# - allow re-using same value for several nodes
/=+===============================+=\
/ : : \
)==: MULTIPLY LINKED LIST :==(
\ :_______________________________: /
\=+===============================+=/
MULTIPLY LINKED LIST ==> #Linked list where:
# - each node has N links
# - each specific set of links performs a full iteration, but most likely in different orders
# - e.g. sorted according to different attributes
#Pros:
# - allows more types of iteration
#Cons:
# - takes more space
# - is not persistent nor recursive
DOUBLY LINKED LIST ==> #Multiply linked list where each node includes a "previous link" to previous node.
#"Next|previous" links are also called "car" and "cdr"
#"XOR linked list":
# - storing single link "next" xor "previous"
# - can access either because [reverse] iteration should know about either next|previous
# - can also use addition or substraction, although they have overflow issues
# - pro: take less space
# - cons:
# - insert|delete requires recomputing links of previous and next node
# - must keep state, i.e. address about previously iterated node
# - more complex to follow the link
ASYMMETRIC DOUBLY LINKED LIST ==> #Multiply linked list where each node includes a link to itself.
#Goal: can perform insertBefore|deleteBefore operations without keeping state about previous node
/=+===============================+=\
/ : : \
)==: OTHER :==(
\ :_______________________________: /
\=+===============================+=/
SELF-ORGANIZING LIST ==> #Linked list where nodes are reordered after operations using heuristic,
#to improve average access time.
#Good when time locality of reference is high.
#Because of the cost of reordering, it makes more sense the less uniform the
#probability distribution between elements is.
#Can be:
# - "move to front" (MTF):
# - move accessed element to front
# - "count method":
# - add counter to elements with number of accesses
# - on access|insert, reorder according to counters
# - compared to MTF:
# - follows long-term probability distribution instead of short-term:
# - pro: less sensitive to elements accessed only once being given high priority
# ("over-rewarding")
# - con: takes more time when distribution changes often
# - O(n) space for the counter
# - "transpose":
# - move accessed elements one position ahead
# - pros|cons: midway between MTF and count method
/=+===============================+=\
/ : : \
)==: COMPOSITION :==(
\ :_______________________________: /
\=+===============================+=/
UNROLLED LINKED LIST ==> #Linked list where values are random access arrays
#Mixes pros|cons of random access arrays and linked lists
#Often random access arrays have fixed size meant to fit in cache lines.
#When inserting new nodes, can reallocate half of elements from previous node to minimize
#fragmentation.
RANDOM ACCESS LIST ==> #Linked list where values are search trees
#Mixes pros|cons of search trees and linked lists
HASH LINKING ==> #Interleaving (see aggregate theory) links in a separate random access array.
#Mixes pros|cons of random access array for links with pros|cons of linked list for values:
# - more time efficient and better locality of reference, since links are usually iterated together
# - slower time allocation and insert|delete than linked list,
# but faster than if values were in random access array too
# - not persistent
ARRAY OF NODES ==> #Implementing a linked list with an array and replacing links by offsets.
#Same pros|cons as linked list except:
# - memory allocation is same as dynamic array
# - length() can be O(1) unless fragmentation is allowed
# - offsets might take less or more space than pointers, depending on how big array is