Single Linked Lists - Curso de Ciencias de la Computación

Apuntes curso CS50, Single linked lists

1. Singly-Linked Lists

2. Singly-Linked Lists
•So far in the course, we’ve only had one kind of data structure
for representing collections of like values.
•structs, recall, give us “containers” for holding variables of different
data types, typically.
•Arrays are great for element lookup, but unless we want to
insert at the very end of the array, inserting elements is quite
costly –remember insertion sort?

3. Singly-Linked Lists
•Arrays also suffer from a great inflexibility –what happens if
we need a larger array than we thought?
•Through clever use of pointers, dynamic memory allocation,
and structs, we can put those two pieces together to
develop a new kind of data structure that gives us the ability to
grow and shrink a collection of like values to fit our needs.

4. Singly-Linked Lists
•We call this combination of elements, when used in this way, a
linked list.
•A linked list nodeis a special kind of structwith two members:
•Data of some data type (int, char, float…)
•A pointer to another node of the same type
•In this way, a set of nodes together can be thought of as
forming a chain of elements that we can follow from beginning
to end.

5. Singly-Linked Lists
typedefstructsllist
{
VALUE val;
structsllist* next;
}
sllnode;

6. Singly-Linked Lists
typedefstructsllist
{
VALUEval;
structsllist* next;
}
sllnode;

7. Singly-Linked Lists
typedefstructsllist
{
VALUE val;
structsllist* next;
}
sllnode;

8. Singly-Linked Lists
typedefstructsllist
{
VALUE val;
structsllist* next;
}
sllnode;

9. Singly-Linked Lists
•In order to work with linked lists effectively, there are a
number of operations that we need to understand:
1.Create a linked list when it doesn’t already exist.
2.Search through a linked list to find an element.
3.Insert a new node into the linked list.
4.Delete a single element from a linked list.
5.Delete an entire linked list.

10. Singly-Linked Lists
•Create a linked list.
sllnode* create(VALUE val);

11. Singly-Linked Lists
•Create a linked list.
sllnode* create(VALUE val);
•Steps involved:
a.Dynamically allocate space for a new sllnode.
b.Check to make sure we didn’t run out of memory.
c.Initialize the node’s valfield.
d.Initialize the node’s nextfield.
e.Return a pointer to the newly created sllnode.

12. Singly-Linked Lists
sllnode* new = create(6);
a.Dynamically allocate space for a
new sllnode.
b.Check to make sure we didn’t run
out of memory.
c.Initialize the node’s valfield.
d.Initialize the node’s nextfield.
e.Return a pointer to the newly
created sllnode.

13. Singly-Linked Lists
sllnode* new = create(6);
a.Dynamically allocate space for a
new sllnode.
b.Check to make sure we didn’t run
out of memory.
c.Initialize the node’s valfield.
d.Initialize the node’s nextfield.
e.Return a pointer to the newly
created sllnode.

14. Singly-Linked Lists
sllnode* new = create(6);
a.Dynamically allocate space for a
new sllnode.
b.Check to make sure we didn’t run
out of memory.
c.Initialize the node’s valfield.
d.Initialize the node’s nextfield.
e.Return a pointer to the newly
created sllnode.
6

15. Singly-Linked Lists
sllnode* new = create(6);
a.Dynamically allocate space for a
new sllnode.
b.Check to make sure we didn’t run
out of memory.
c.Initialize the node’s valfield.
d.Initialize the node’s nextfield.
e.Return a pointer to the newly
created sllnode.
6

16. Singly-Linked Lists
sllnode* new = create(6);
a.Dynamically allocate space for a
new sllnode.
b.Check to make sure we didn’t run
out of memory.
c.Initialize the node’s valfield.
d.Initialize the node’s nextfield.
e.Return a pointer to the newly
created sllnode.
6
new

17. Singly-Linked Lists
•Search through a linked list to find an element.
bool find(sllnode* head, VALUE val);

18. Singly-Linked Lists
•Search through a linked list to find an element.
bool find(sllnode* head, VALUE val);
•Steps involved:
a.Create a traversal pointer pointing to the list’s head.
b.If the current node’s valfield is what we’re looking for, report
success.
c.If not, set the traversal pointer to the next pointer in the list and go
back to step b.
d.If you’ve reached the end of the list, report failure.

19. Singly-Linked Lists
bool exists = find(list, 6);
2 3 5 6 8
list

20. Singly-Linked Lists
bool exists = find(list, 6);
2 3 5 6 8
list
trav

21. Singly-Linked Lists
bool exists = find(list, 6);
2 3 5 6 8
list
trav

22. Singly-Linked Lists
bool exists = find(list, 6);
2 3 5 6 8
list
trav

23. Singly-Linked Lists
bool exists = find(list, 6);
2 3 5 6 8
list
trav

24. Singly-Linked Lists
bool exists = find(list, 6);
2 7 5 3 8
list

25. Singly-Linked Lists
bool exists = find(list, 6);
2 7 5 3 8
list
trav

26. Singly-Linked Lists
bool exists = find(list, 6);
2 7 5 3 8
list
trav

27. Singly-Linked Lists
bool exists = find(list, 6);
2 7 5 3 8
list
trav

28. Singly-Linked Lists
bool exists = find(list, 6);
2 7 5 3 8
list
trav

29. Singly-Linked Lists
bool exists = find(list, 6);
2 7 5 3 8
list
trav

30. Singly-Linked Lists
•Insert a new node into the linked list.
sllnode* insert(sllnode* head, VALUE val);

31. Singly-Linked Lists
•Insert a new node into the linked list.
sllnode* insert(sllnode* head, VALUE val);
•Steps involved:
a.Dynamically allocate space for a new sllnode.
b.Check to make sure we didn’t run out of memory.
c.Populate and insert the node at the beginning of the linked list.
d.Return a pointer to the new head of the linked list.

32. Singly-Linked Lists
•Insert a new node into the linked list.
sllnode* insert(sllnode* head, VALUE val);
•Steps involved:
a.Dynamically allocate space for a new sllnode.
b.Check to make sure we didn’t run out of memory.
c.Populate and insert the node at the beginning of the linked list.
d.Return a pointer to the new head of the linked list.

33. Singly-Linked Lists
list = insert(list, 12);
15 9 13 10
list

34. Singly-Linked Lists
list = insert(list, 12);
15 9 13 10
list
new

35. Singly-Linked Lists
list = insert(list, 12);
12 15 9 13 10
list
new

36. Singly-Linked Lists
•Decision time!
•Which pointer should we move first? Should the “12” node be
the new head of the linked list, since it now exists, or should
we connect it to the list first?
•This is one of the trickiest things with linked lists. Order
matters!

37. Singly-Linked Lists
list = insert(list, 12);
12 15 9 13 10
list
new

38. Singly-Linked Lists
list = insert(list, 12);
12 15 9 13 10
list
new

39. Singly-Linked Lists
list = insert(list, 12);
12 15 9 13 10
?
list
new

40. Singly-Linked Lists
list = insert(list, 12);
12 15 9 13 10
list
new

41. Singly-Linked Lists
list = insert(list, 12);
12 15 9 13 10
list
new

42. Singly-Linked Lists
list = insert(list, 12);
12 15 9 13 10
list
new

43. Singly-Linked Lists
•Delete an entire linked list.
void destroy(sllnode* head);

44. Singly-Linked Lists
•Delete an entire linked list.
void destroy(sllnode* head);
•Steps involved:
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.

45. Singly-Linked Lists
•Delete an entire linked list.
void destroy(sllnode* head);
•Steps involved:
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.

46. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list

47. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list

48. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list

49. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list

50. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list

51. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list

52. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list

53. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list

54. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list list

55. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list list

56. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list list
list

57. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list list
list

58. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list list

59. Singly-Linked Lists
12 15 9 13 10
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list list

60. Singly-Linked Lists
12 15 9 13
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list

61. Singly-Linked Lists
12 15 9 13
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list list

62. Singly-Linked Lists
12 15 9
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list

63. Singly-Linked Lists
12 15 9
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list list

64. Singly-Linked Lists
12 15
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list

65. Singly-Linked Lists
12 15
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list list

66. Singly-Linked Lists
12
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list

67. Singly-Linked Lists
12
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);
list

68. Singly-Linked Lists
destroy()
destroy()
destroy()
destroy()
destroy()
destroy()
STACK FRAMES
a.If you’ve reached a null pointer, stop.
b.Delete the rest of the list.
c.Free the current node.
destroy(list);

69. Singly-Linked Lists
•In order to work with linked lists effectively, there are a
number of operations that we need to understand:
1.Create a linked list when it doesn’t already exist.
2.Search through a linked list to find an element.
3.Insert a new node into the linked list.
4.Delete a single element from a linked list.
5.Delete an entire linked list.