Class Notes (1,100,000)
CA (620,000)
UW (20,000)
CS (1,000)
CS234 (30)
Lecture 8

CS234 Lecture Notes - Lecture 8: Linked List, Time Complexity, Doubly Linked List


Department
Computer Science
Course Code
CS234
Professor
Mirza Beg
Lecture
8

Page:
of 5
Lecture 8 May 30
Linked Structures
Python List:
1. Adjustable size (requires allocation of new array)
L = [ None ] * 1,000,0000 <- possible waste of space
2. Constant time random access
L[i]
-> contiguous block of memory space
3. Insertions and deletions may take linear time in the worst case
Linked Structures:
1. Adjustable size (allocate space as required)
- Memory space is not contagious
2. Random access of items is linear in the worst case
3. Insertions and deletions can be constant time
Linked Structures:
- Are used to store elements in a collection
- Maybe appropriate here the algorith is isert – delete itesie
- Constructive using nodes
Node
Data Link
- Each node contains some data and at least one reference or link to another node
Linked Lists (Simply linked list)
- A structure where the nodes are linked together in a linear order
9
17
14
67
Head
- Head reference to the first node in the list
- Tail the last node in the list
Class Node:
def __init__(self, item, next = Nonde):
self.item = item
self.next = next
def __repr__(self):
return str(self.item)
Most nodes do not have names or references. They are references by links in same precedence
Node.
Head:
o Should have an external reference
o Entry point in the list
o Null indicates an empty list
head = Node(9, Node(14, Node(17, Node(67, None))))
Head
9
17
14
67
n = Node(23)
23
node
Basic List Operations:
1. List traversal
2. Searching for a value
3. Insert a value
4. Remove a value
List Traversal:
9
14
17
67
Head
- Use a temporary reference to traverse the list
Head
9
14
17
67
curNode curNode curNode
Travese the list by advancing curNode reference
curNode = curNode.next
Repeat this until curNode == None, i.e. reached the end of the list
def traversal(heat):
curNode = head
while curNode != None
print curNode
curNode = curNode.next
Search for an item
Traversal of the list
- Produces true if item is found
- Produces False otherwise
Insert an item into a SLL:
Insert(23) -> Node(23)
1. Insert in the beginning:
newNode Head
2
23
1
9
14
17
67
newNode.next = head
head = newNode O(n)
9
14
17
67
Inser(0,23)