Class Notes (835,730)
Canada (509,354)
CSC148H1 (92)
Paul Gries (18)
Lecture

march28c.docx

3 Pages
135 Views
Unlock Document

Department
Computer Science
Course
CSC148H1
Professor
Paul Gries
Semester
Winter

Description
1. class LinkedList(object): 2. 3. class Node(object): 4. def __init__(self, val): 5. self.data = val 6. self.next = None 7. 8. def __init__(self): 9. '''A new empty linked list.''' 10. self.contents = None 11. 12. def insert(self, v, i): 13. '''(LinkedList, object, int) -> NoneType 14. Insert v at index i into this list.''' 15. 16. # Find the node that I want to insert *after*. 17. if i == 0: 18. n = LinkedList.Node(v) 19. n.next = self.contents 20. self.contents = n 21. else: 22. # Find the previous node. 23. t = self.contents 24. for k in range(i - 1): 25. t = t.next 26. n = LinkedList.Node(v) 27. n.next = t.next 28. t.next = n 29. 30. def append(self, v): 31. '''(LinkedList, object) -> NoneType 32. Append v to the end of this list.''' 33. 34. self.insert(v, len(self)) 35. 36. def get(self, i): 37. '''(LinkedList, int) -> object 38. Return the item at index i.''' 39. t = self.contents 40. for k in range(i): 41. t = t.next 42. return t.data 43. 44. def remove(self, i): 45. '''(LinkedList, int) -> object 46. Remove and return the item at index i in this 47. list.''' 48. 49. if i == 0: 50. res = self.contents.data 51. self.contents = self.contents.next 52. else: 53. t = self.contents 54. for k in range(i - 1): 55. t = t.next 56. 57. res = t.next.data 58. t.next = t.next.next 59. 60. return res 61. 62. def __getitem__(self, i): 63. '''(LinkedList, int or slice) -> object 64. Return the item at index i if i in an int, or 65. a LinkedList if i is a slice.''' 66. if not isinstance(i, slice): 67. t = self.contents 68. for k in range(i): 69. t = t.next 70. 71. return t.data 72. else: 73. res = LinkedList() 74. start, stop, step = i.indices(len(self)) 75. # Assume step is 1. 76. 77. # Find the start. 78. t = self.contents 79. for k in range(start): 80. t = t.next 81. 82. # Gather the items in the slice. 83. for i in range(stop - start): 84. res.append(t.data) 85. t = t.next 86. 87. return res 88. 89. def __setitem__(self, i, v): 90. '''(LinkedList, int, object) -> object 91. Replace the item at index i with v.''' 92. t = self.contents 93. for k in range(i): 94. t = t.next 95. 96. t.data = v 97. 98. def __iter__(self): 99. '''(LinkedList) -> obj
More Less

Related notes for CSC148H1

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit