Linked Lists
• DSSL2 Q&A • Linked lists
Copyright By PowCoder代写 加微信 powcoder
Linked lists
A problem with vectors
What if we want to add 6 between 5 and 7?
No can do! Vector is full. What do we do?
Need to create a new, bigger vector, and copy everything over…
(One) Solution: Linked Lists
• You’ve seen those in 111/211
cons creates a pair
Thedatafieldholdsonedataelement
(sometimescalledcarorfirst)
The next field holds an arrow to the next node in the list
(sometimescalledcdrorrest)
data data data data next next next next
(One) Solution: Linked Lists
• Inserting in the middle? No problem! Just change the arrows
Inserting at the beginning
data data data data data data data next next next next next next next
• Even easier! Just add a new node
Inserting at the beginning
data data data data data data data data next next next next next next next next
• Even easier! Just add a new node
Indirection
data data data data data data data data next next next next next next next next
• Better: have list be a header pointing to the first node Then can change the header not the variable!
Header is within the DS, DS operations can change it!
Variable is outside the DS, must rely on client to change…
Removing at the beginning
data data data data data data data data next next next next next next next next
• Change the header to point to the next of the current head • What happens to the former head?
In C, you’d have to explicitly deallocate it
In DSSL2 (and Python, and 95% of languages), you don’t!
(garbage collection)
Stop! Question time!
Before we move on to an implementation in DSSL2…
Anything unclear so far? Anything I missed?
Now in DSSL2
Linked lists in DSSL2
# Link is one of:
# – node { data: Number, next: Link }
struct node:
class SLL:
def __init__(self):
self.head = None
def push_front(self, data):
self.head = node(data, self.head)
List operations in DSSL2
class SLL: …
def get_front(self):
if node?(self.head): return self.head.data
else: error(’empty list’)
def get_nth(self, n):
let curr = self.head
while not curr == None:
if n == 0:
return curr.data
curr = curr.next
error(‘list too short’)
List operations in DSSL2
class SLL: …
def get_front(self):
if node?(self.head): return self.head.data
else: error(’empty list’)
def get_nth(self, n):
let curr = self.head
while not curr == None:
if n == 0:
return curr.data
curr = curr.next
error(‘list too short’)
What about set_nth?
More DSSL2 list operations
class SLL: …
def _find_nth_node(self, n):
let curr = self.head
while not curr == None:
if n == 0:
return curr
curr = curr.next
error(‘list too short’)
def get_nth(self, n):
return self._find_nth_node(n).data
def set_nth(self, n, val):
self._find_nth_node(n).data = val
# leading _ → private
What else might we want to do?
• Know how long the list is without counting. • Insert or remove at the end.
Keeping the length
Have the header store the length!
data data data data next next next next
data data next next
QUIZ: How can we make sure the len field is always right? By having all adds and removes update the length! (This is an example of an invariant.)
Quick access to the tail
Keep a pointer to the last link!
head tail len
data data data next next next
data data data next next next
QUIZ: Name some operations that are less work now. Get/set last, append, etc.
QUIZ: Name some that are still more work. Get/set nth, split, etc. Also: remove last!
Doubly-linked
Can reach next to last via prev of tail!
head tail len
data data prev prev next next
data data data data prev prev prev prev next next next next
QUIZ: What are some invariants for a doubly-linked list?
Doubly-linked
Can reach next to last via prev of tail!
head tail len
data data prev prev next next
data data data data prev prev prev prev next next next next
QUIZ: What are some invariants for a doubly-linked list?
prev of our next is us, and vice versa.
head has no prev. tail has no next. (Lots of edge cases… Tricky to get right.)
Removing at the end
head tail len
data data data prev prev prev next next next
data data data prev prev prev next next next
QUIZ: what are the three things that changed?
• tail now points to 5 node. • next of 5 node is now null. • len is decremented.
Invariants galore! Gotta respect ’em all!
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
• Dynamic arrays: another data structure!
Allocate a vector with some empty space at the end
Can add elements to the end until we’re full
Then allocate bigger vector, copy elements, and keep going
Doubling size is efficient (see lectures 6 and 17)
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
• Dynamic arrays: another data structure!
Allocate a vector with some empty space at the end
Can add elements to the end until we’re full
Then allocate bigger vector, copy elements, and keep going
Doubling size is efficient (see lectures 6 and 17)
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
• Dynamic arrays: another data structure!
Allocate a vector with some empty space at the end
Can add elements to the end until we’re full
Then allocate bigger vector, copy elements, and keep going
Doubling size is efficient (see lectures 6 and 17)
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
• Dynamic arrays: another data structure!
Allocate a vector with some empty space at the end
Can add elements to the end until we’re full
Then allocate bigger vector, copy elements, and keep going
Doubling size is efficient (see lectures 6 and 17)
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
• Dynamic arrays: another data structure!
Allocate a vector with some empty space at the end
Can add elements to the end until we’re full
Then allocate bigger vector, copy elements, and keep going
Doubling size is efficient (see lectures 6 and 17)
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
• Dynamic arrays: another data structure!
Allocate a vector with some empty space at the end
Can add elements to the end until we’re full
Then allocate bigger vector, copy elements, and keep going
Doubling size is efficient (see lectures 6 and 17)
Addendum: There is hope for vectors
• Individual vectors have a fixed size, cannot change
• But we can build a growable data structure using vectors!
• Dynamic arrays: another data structure!
Allocate a vector with some empty space at the end
Can add elements to the end until we’re full
Then allocate bigger vector, copy elements, and keep going
Doubling size is efficient (see lectures 6 and 17) data
std::vector in C++, ArrayList in Java, and list in Python!
If we have time: adding operations to SLL code
Next time: abstract data types
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com