Transcript Singly-linked List

Linked Lists

A linked list is a sequence in which there is
a defined order as with any sequence but
unlike array and Vector there is no
property of contiguity of memory.
1
Singly-linked Lists
A list in which there is a preferred direction.
 A minimally linked list.
 The item before has a pointer to the item
after.

2
Singly-linked List

Implement this structure using objects and
references.
3
Singly-linked List
4
11
1
7
head
4
Singly-linked List
4
11
1
7
head
5
Singly-linked List
class ListElement
{
Object datum ;
ListElement nextElement ;
. . .
}
datum
nextElement
6
Singly-linked List
ListElement newItem =
new ListElement(new Integer(4)) ;
ListElement p = null ;
ListElement c = head ;
while ((c != null) && !c.datum.lessThan(newItem))
{
p = c ;
c = c.nextElement ;
}
newItem.nextElement = c ;
p.nextElement = newItem ;
7
Singly-linked List
newElement
p
c
4
11
1
7
head
8
Analysing Singly-linked List
Accessing a given location is O(n).
 Setting a given location is O(n).
 Inserting a new item is O(n).
 Deleting an item is O(n)
 Assuming both a head at a tail pointer,
accessing, inserting or deleting can be O(1).

9
Doubly-linked Lists
A list without a preferred direction.
 The links are bidirectional: implement this
with a link in both directions.

10
Doubly-linked List
head
tail
11
Doubly-linked List
head
tail
12
Doubly-linked List
class ListElement
{
Object datum ;
ListElement nextElement ;
ListElement previousElement ;
previousElement
. . .
}
datum
nextElement
13
Doubly-linked List
ListElement newItem =
new ListElement(new Integer(4)) ;
ListElement c = head ;
while ((c.next != null) &&
!c.next.datum.lessThan(newItem))
{
Spot the deliberate
c = c.nextElement ;
mistake. What needs to
be done to correct this?
}
newItem.nextElement = c.nextElement ;
newItem.previousElement = c ;
c.nextElement.previousElement = newItem ;
c.nextElement = newItem ;
14
Doubly-linked List
head
c
newItem
tail
15
Doubly-linked List
Performance of doubly-linked list is
formally similar to singly linked list.
 The complexity of managing two pointers
makes things very much easier since we
only ever need a single pointer into the list.
 Iterators and editing are made easy.

16
Doubly-linked List
Usually find the List type in a package is a
doubly-linked list.
 Singly-linked list are used in other data
structures.

17
Stack and Queue

Familiar with the abstractions of stack and
queue.
18
Stack
push
pop
isEmpty
top
19
Queue
isEmpty
insert
remove
20
Implementing Stack
tos
21
Implementing Queue
head
tail
22
Multi-lists
Multi-lists are essentially the technique of
embedding multiple lists into a single data
structure.
 A multi-list has more than one next pointer,
like a doubly linked list, but the pointers
create separate lists.

23
Multi-lists
head
24
Multi-lists
head
25
Multi-lists (Not Required)
head
head
26
Linked Structures
A doubly-linked list or multi-list is a data
structure with multiple pointers in each
node.
 In a doubly-linked list the two pointers
create bi-directional links
 In a multi-list the pointers used to make
multiple link routes through the data.

27
Linked Structures
What else can we do with multiple links?
 Make them point at different data: create
Trees (and Graphs).

28
degree
Trees
root
children
parent
Level 1
Level 2
Level 3
height = depth = 3
node
leaf node
29
Trees

Crucial properties of Trees:
Links only go down from parent to child.
 Each node has one and only one parent (except
root which has no parent).
 There are no links up the data structure; no
child to parent links.
 There are no sibling links; no links between
nodes at the same level.

30
Trees
If we relax the restrictions, it is not a Tree, it
is a Graph.
 A Tree is a directed, acyclic Graph that is
single parent.

31
Trees
Binary Trees have degree 2.
 Red–Black Trees and AVL Trees are Binary
Trees with special extra properties; they are
balanced.
 B-Trees, B+-Trees, B*-Trees are more
complicated Trees with flexible branching
factor: these are used very extensively in
databases.

32
Binary Trees
Trees are immensely useful for sorting and
searching.
 Look at Binary Trees as they are the
simplest.

33
Binary Trees
This is a complete
binary tree.
34
Binary Trees
How to insert something in the list?
 Need a metric, there must be an order
relation defined on the nodes.
 The elements are in the tree in a given
order; assume ascending order.

35
Binary Trees
Inserting an element in the Binary Tree
involves:
 If the tree is empty, insert the element as the
root.

36
Binary Trees

If the tree is not empty:
Start at the root.
 For each node decide whether the element is the
same as the one at the node or comes before or
after it in the defined order.
 When the child is a null pointer insert the
element.

37
Binary Tree
37
root
37
38
Binary Tree
37, 9, 3
root
37
9
3
39
Binary Trees
37, 9, 3, 68, 14, 54
root
37
9
3
68
14
54
40
Binary Trees
Delete this one
41
Binary Trees
42
Binary Trees
Delete this one
43
Binary Trees
Assume ascending
order.
44
Binary Trees
Delete this one
45
Binary Trees
Assume ascending
order.
46
Binary Tree

In Java:
class Unit
{
public Unit(Object o, Unit l, Unit r)
{ datum = o ; left = l ; right = r ; }
Object datum ;
Unit left ;
Unit right ;
}
47
Binary Tree

Copying can be done recursively:
public Object clone()
{
return new Unit(datum,
(left != null) ?
((Unit)left).clone() : null,
(right != null) ?
((Unit)right).clone() : null
) ;
}
48
Binary Tree

Can take a tour around the tree, doing
something at each stage:
void inOrder (Function f)
{
if (left != null) { left.inOrder(f) ; }
f.execute(this) ;
if (right != null) { right.inOrder(f); }
}
49
Binary Tree

Can take a different tour around the tree,
doing something at each stage:
void preOrder (Function f)
{
f.execute(this) ;
if (left != null) { left.preOrder(f) ; }
if (right != null) { right.preOrder(f); }
}
50
Binary Tree

Can take yet another tour around the tree,
doing something at each stage:
void postOrder (Function f)
{
if (left != 0) { left.postOrder(f) ; }
if (right != 0) { right.postOrder(f); }
f.execute(this) ;
}
51
Traversing a Binary Tree

Four sorts of route through a tree:
In-order.
 Pre-order.
 Post-order.
 Level-order.

52
Traversing a Binary Tree
Pre-order, post-order and in-order are
related since they just rearrange order of
behaviour. Depth-first searches.
 Level-order is different. Breadth-first
search.

53
Traversing a Binary Tree
inorder: 3, 9, 14, 37, 54, 68
preorder: 37, 9, 3, 14, 68, 54
postorder: 3, 14, 9, 54, 68, 37
levelorder: 37, 9, 68, 3, 14, 54
root
37
9
3
68
14
54
This is a complete
binary tree.
54
Searching and Sorting
A Tree is an inherently sorted data structure.
 A Tree can be an index to data rather than
holding data.
 Searching using a Tree is much better than
linear search, in fact it is a sort of binary
chop search.

55
Binary Trees

Balance is important when working with
Binary Trees:
Height is O(log2 n) in the best case but O(n) in
the worst case (tree becomes a linear list).
 Worst case occurs when data is fed in in order.
 Lookup time, insertion time and removal time
are all O(log2 n) when the tree is balanced and
O(n) in the worst case (directly proportional to
approximate height).

56
Problem with Binary Tree
If data is entered in sorted order, the tree
becomes a list.
 This degeneration loses the O(log2 n)
behaviour.
 How can we get around this?

57
Problem with Binary Tree

Make the tree self-balancing.
58
AVL Tree
A binary tree that is self-modifying.
 Is nearly balanced at all times.
 No sub-tree is more than one level deeper
than its sibling.
 Adelson-Velskii and Landis were the
progenitors.

59
AVL Tree

AVL trees insert data by inserting as any
normal binary tree.
 The tree may become unbalanced.
 Thus, there is then a second stage, the tree
re-balances itself if it needs to.
60
AVL Tree
When removal occurs, the tree may become
unbalanced.
 There is, therefore, a second stage, the tree
re-balances itself if it needs to.

61
AVL Tree

AVL trees are now considered inefficient
and are therefore rarely used.
 Trees are, however, so important that
efficiency is necessary.
62
Red-Black Tree
These trees have a different algorithm for
handling the modifications.
 Instead of measuring the unbalancedness of
the tree, each node is coloured.

63
Red-Black Tree
Insertion does not require two phases since
the tree can be re-balanced as the position
of the insertion point is found.
 This makes it far more efficient than the
AVL tree.

64
B-Tree
Used in database systems.
 Not used in memory bound systems.

65
End of this Session
66