Class Notes (806,720)
Canada (492,424)
CS 234 (31)


5 Pages
Unlock Document

University of Waterloo
Computer Science
CS 234
Robert Sproule

Lec08 - Linked Structures Python List (Review) 1. Adjustable size (it may require allocation of a new array) a. L = [None] * 100000 2. Constant time access, L[i], O(1) 3. Insertions and Deletions may take linear time, O(n) a. Example: L.pop(i) i. L.pop(0) which removes the first element and copies everything after it to the left Linked Structures 1. Adjustable size (memory allocated when needed) a. Memory space allocated for linked structures may not be contiguous 2. Random access is linear in the worst case, O(n) 3. Insertions and Deletions may become constant time, O(1) a. Depending how you insert and delete it 1. They are used to store a collection of items 2. Linked structures may be appropriate in certain cases 3. Linked structures are created using Nodes. a. First box = data/item; Second box = link(s) 4. Each node contains some data and one or more links to other nodes Linked Structure (singly linked list) - A linked list is one in which nodes are linked together in a linear order o o head – reference to the first node in the list o tail – last node in the list § link in the tail is a None reference class Node: def __init__(self,item,next=None): self.item = item = next # if .next is not assigned, None will automatically be assigned def __repr__(self): return str(self.item) Most nodes have no names or references. They are referenced by the link in the preceding node. head - should be referenced by the external variable - entry point to the list - null head reference indicates an empty list The basic operations 1. List traversal 2. Search for an item 3. Insert an item 4. Delete an item Traversing a list Create a linked list n = Node(23) LL = Node(9,(Node(14,Node(17,Node(52)))) We can traver
More Less

Related notes for CS 234

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


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.