Transcript 10 Introduction to Linked Structures

Computer Science 112
Fundamentals of Programming II
Introduction to Linked Structures
Basic Array Operations
Constructor:
Array(size, fillValue = None)
Length:
len(a)
Access:
a[index]
Replacement:
a[index] = newValue
Iteration:
for value in a:
Search:
value in a
Elements can be of any type
[] has a precondition on the index
Problems With Arrays
• Insertions and deletions require shifting
elements, an O(n) operation
• Length is fixed at instantiation, resizing
requires new memory and transfer of
elements
Why We Have These Problems
• Array cells map to adjacent cells in memory, to
support constant-time access
• There is a one-to-one correspondence between the
logical structure of the sequence of elements and
the underlying memory storage
• If we can decouple the logical sequence and the
memory representation, we might solve these
problems
Linked Structures
D1
D2
D3
D4
A linked structure allows us to represent a sequence of
elements independently of their positions in memory
Linked structures support insertions, deletions, and
traversals, but not random access
Storage is allocated for each new element, as needed,
from an area of memory called the system heap
Linked Structures
A linked structure consists of a unique external link.
Linked Structures
D1
D2
D3
A linked structure consists of a unique external link.
This link is either empty or points to a node.
A node contains two parts:
a data element
a link to the next node
Linked Structures
D1
D2
D3
D4
A linked structure consists of a unique external link.
This link is either empty or points to a node.
A node contains two parts:
a data element
a link to the next node
The last node in a linked structure contains an empty link
Arrays and Computer Memory
numbers
3 6 5
0 1 2 3 4
Memory address of numbers[2] =
65534
65535
3
6
5
0
2
...
656 + 2 = 658
656
657
658
659
660
...
base address in numbers + 2 =
2
0
656
...
The array cells are adjacent in memory
0
1
2
...
The variable numbers contains the
address of the first cell in the array
10
9
Nodes and Computer Memory
6
5
0
1
2
656
657
658
659
660
65534
65535
6
658
5
0
2
...
...
The variable numbers contains the
address of the first node in the linked
structure
...
3
2
1
65534
...
numbers
0
1
2
3
656
Nodes and Computer Memory
5
0
1
2
The address of the second node is
contained in the previous node’s next link
656
657
658
659
660
2
1
65534
...
6
numbers
...
3
0
1
2
...
...
65534
65535
6
658
5
0
2
3
656
Nodes and Computer Memory
6
5
0
1
2
The last node’s next link is None, which
is the memory address 0
...
3
2
1
65534
...
numbers
0
1
2
656
657
658
659
660
...
...
65534
65535
6
658
5
0
2
3
656
An Empty External link
When there are no data, there are no nodes and the external
link is empty
Links are sometimes called pointers or references
References in Python are either None or refer to objects
A node will be a new type of object
Linked Structures
D1
When a data element is inserted, we create a new node, set
its data field to the data element, and set its link to None.
A Node Class
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
Usually a utility class to be used within a client class
No need for accessor or mutator methods
The data can be any Python object
The next is always either another node or None
Declaring an External Pointer
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = None
head just contains an empty link or None pointer
head
Adding a Node
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = Node("A", None)
head contains a link or reference to a node
head
“A”
Display the Data Element
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = Node("A", None)
print(head.data)
Displays the letter “A”
head
“A”
Adding and Accessing a Second Node
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = Node("A", Node("B", None))
print(head.next.data)
Displays the letter “B”
head
“A”
“B”
Type Exception on None
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = Node("A", None)
print(head.next.data)
Raises an exception: None has no data field
head
“A”
Prepend 5 Data Elements
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = None
for i in range(1, 6):
head = Node(i, head)
head
Prepend 5 Data Elements
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = None
for i in range(1, 6):
head = Node(i, head)
head
1
Prepend 5 Data Elements
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = None
for i in range(1, 6):
head = Node(i, head)
head
2
1
Prepend 5 Data Elements
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = None
for i in range(1, 6):
head = Node(i, head)
head
3
2
1
Prepend 5 Data Elements
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = None
for i in range(1, 6):
head = Node(i, head)
head
4
3
2
1
Prepend 5 Data Elements
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = None
for i in range(1, 6):
head = Node(i, head)
head
5
4
3
2
1
Traverse the Structure
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = <prepend 5 elements>
probe = head
while probe != None:
print(probe.data)
probe = probe.next
head
probe
5
4
3
2
1
Traverse the Structure
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = <prepend 5 elements>
probe = head
while probe != None:
print(probe.data)
probe = probe.next
head
probe
5
4
3
2
1
Traverse the Structure
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = <prepend 5 elements>
probe = head
while probe != None:
print(probe.data)
probe = probe.next
head
probe
5
4
3
2
1
Traverse the Structure
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = <prepend 5 elements>
probe = head
while probe != None:
print(probe.data)
probe = probe.next
head
probe
5
4
3
2
1
Traverse the Structure
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = <prepend 5 elements>
probe = head
while probe != None:
print(probe.data)
probe = probe.next
head
probe
5
4
3
2
1
Traverse the Structure
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
head = <prepend 5 elements>
probe = head
while probe != None:
print(probe.data)
probe = probe.next
head
probe
5
4
3
2
1
Delete the First Element (Node)
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
if head != None:
head = head.next
head
5
4
3
2
1
Delete the First Element (Node)
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
The deleted node
cannot be referenced,
so the garbage
collector will return
it to the system
memory
if head != None:
head = head.next
head
5
4
3
2
1
Clear the Structure
class Node(object):
def __init__(self, data, next = None):
self.data = data
self.next = next
The deleted nodes
cannot be referenced,
so the garbage
collector will return
them all to the
system memory
head = None
head
5
4
3
2
1
Memory as Needed
• The logical size and the physical size of the
structure are always the same
• Memory is allocated for new nodes only
when needed
• Storage for deleted nodes is reclaimed by
the system
Analysis of Insert and Remove
at the Head
• Use of memory is always O(1)
• No movement of data within the structure,
just rearrange a couple of links, O(1)
running time
• Quite the opposite behavior of arrays
Insert at the End
(Append an Element)
• If the head pointer is empty, just assign it a
new node
• Otherwise,
– chain down the links until you reach the pointer
to the last node
– Set the last node’s next pointer to a new node
Insert at the End
(Append an Element)
newNode = Node(1, None)
if head == None:
head = newNode
else:
probe = head
while probe.next != None:
probe = probe.next
probe.next = newNode
newNode
head
probe
5
4
3
2
1
Insert at the End
(Append an Element)
newNode = Node(1, None)
if head == None:
head = newNode
else:
probe = head
while probe.next != None:
probe = probe.next
probe.next = newNode
newNode
head
probe
5
4
3
2
1
Insert at the End
(Append an Element)
newNode = Node(1, None)
if head == None:
head = newNode
else:
probe = head
while probe.next != None:
probe = probe.next
probe.next = newNode
newNode
head
probe
5
4
3
2
1
Insert at the End
(Append an Element)
newNode = Node(1, None)
if head == None:
head = newNode
else:
probe = head
while probe.next != None:
probe = probe.next
probe.next = newNode
newNode
head
probe
5
4
3
2
1
Insert at the End
(Append an Element)
newNode = Node(1, None)
if head == None:
head = newNode
else:
probe = head
while probe.next != None:
probe = probe.next
probe.next = newNode
newNode
head
probe
5
4
3
2
1
Insert at (before) the ith Position
i = 2
if head == None or i == 0:
head = Node(1, head)
else:
probe = head
while i > 1 and probe.next != None:
probe = probe.next
i -= 1
probe.next = Node(1, probe.next)
head
probe
5
4
0
3
1
2
2
3
Insert at the ith Position
i = 2
if head == None or i == 0:
head = Node(1, head)
else:
probe = head
while i > 1 and probe.next != None:
probe = probe.next
i -= 1
probe.next = Node(1, probe.next)
head
probe
5
4
0
3
1
2
2
3
Insert at the ith Position
i = 2
if head == None or i == 0:
head = Node(1, head)
else:
probe = head
while i > 1 and probe.next != None:
probe = probe.next
i -= 1
probe.next = Node(1, probe.next)
newNode
head
probe
5
1
4
0
3
1
2
2
3
Analysis of Insertions
• Use of memory is O(1)
• No movement of data within the structure, just
rearrange a couple of links
• Append at the end and insert at the ith position are
both O(n), because we must chain down the links
• Same behavior for removals, accesses, and
replacements at the ith position
Tradeoffs: Array or Linked Structure?
numbers
5
0
numCount 4
numbers
5
4
4
1
3
2
2
3
3
4
2
Tradeoffs
• Arrays:
– Constant-time access is good for binary search,
implementing a dictionary, etc.
– Uses less memory if the array is close to full
• Linked structures:
– Uses memory only as needed, never have to resize
– Insertions and removals need no extra overhead to shift
data elements
– But accesses, replacements, insertions, and removals at
arbitrary positions are linear time operations
For Wednesday
Interfaces and Implementations
Chapter 5