CS代写 CSE 10 - PowCoder代写

Linked Data Structures I: Singly-Linked Lists
1 October 2020 OSU CSE 1

What’s Wrong With Arrays?

• A Java array is not ideally suited as a data representation of the various collection types
– Similarly for the Java collections framework
1 October 2020 OSU CSE 2

What’s Wrong With Arrays?
• A Java array is not ideally suited as a data representation of the various collection types
– Similarly for the Java collections framework
Any type whose abstract mathematical model involves a string or set or multiset (or tree or binary tree?) is a “collection” type.
1 October 2020

What’s Wrong With Arrays?
• A Java array is not ideally suited as a data representation of the various collection types
– Similarly for the Java collections framework
Examples are Queue, Stack, Sequence, Set, Map, SortingMachine, …
1 October 2020 OSU CSE 4

What’s Wrong With Arrays?
• A Java array is not ideally suited as a data representation of the various collection types
– Similarly for the Java collections framework This is part of the package
java.util, and includes many types similar to the
OSU CSE components.
1 October 2020 OSU CSE 5

Collection Terminology
• Fixed size means the size/length of a collection is “inflexible”, i.e., it is determined at initialization of the collection and cannot be incrementally adjusted
– A classical synonym is static; this term unfortunately means other things in Java
• Dynamic means the size/length of a collection is “flexible”, i.e., it can be
incrementally adjusted by “adding” and “removing” entries, even from the middle
1 October 2020 OSU CSE 6

Collection Terminology
• Direct access means the entries of a collection (typically with a string model) may be accessed by providing an int position/index of any entry in the collection
– A classical but unfortunate synonym is random access; nothing random about it!
• Sequential access means the entries of a collection (with a string model) may be
accessed in increasing order of position by accessing the “next” entry in the collection
1 October 2020 OSU CSE 7

Collection Terminology
We might say any
collection with an iterator • Direct access means the entries of a
allows sequential access, collection (typically with a string model)
but this is about the other may be accessed by providing an int
methods for access. position/index of any entry in the collection
– A classical but unfortunate synonym is random access; nothing random about it!
• Sequential access means the entries of a collection (with a string model) may be
accessed in increasing order of position by accessing the “next” entry in the collection
1 October 2020 OSU CSE 8

Key Pros and Cons of Arrays • Pros:
– Direct access is fast, i.e., it takes constant time independent of the length of the array
– Its fixed size limits array utility where dynamic size is important: it can run out of room
– Adding and removing entries in the middle requires moving array entries, which is slow
– Initialization may be expensive, especially if many entries are not subsequently used
1 October 2020 OSU CSE 9

Fixed Size Can Support Fast Direct Access
• A Java array is represented in a
contiguous block of memory locations
with consecutive memory addresses (IDs),
so the memory address of the entry at index i can be directly calculated from
the memory address of the first entry, by using simple arithmetic
1 October 2020 OSU CSE 10

Client’s view of an array
(entries = <13, 18, 6, 21, 12, 21>):
length = 6
Implementer’s view of an array in memory:
45 46 47 48 49 50
1 October 2020
base = 45, length = 6

If client wants to
Client’s view of an array
(entries = <13, 18, 6, 21, 12, 21>):
access the entry at
position 3 of the array,
how does implementer compute its memory
length = 6
Implementer’s view of an array in memory:
address/ID?
45 46 47 48 49 50
1 October 2020
base = 45, length = 6

Every modern
computer the JVM
Client’s view of an array
(entries = <13, 18, 6, 21, 12, 21>):
runs on provides
constant-time access
to any memory location given the
length = 6
Implementer’s view of an array in memory:
memory address/ID.
45 46 47 48 49 50
1 October 2020
base = 45, length = 6

Notice the Array Mismatches
Collection
Fixed Size?
Direct Access?
Seq Access?
1 October 2020 OSU CSE 14

What Can Be Done?
• To represent collections that are dynamic with sequential access, a different approach is needed: not arrays
– Note: It is an open problem to represent a Sequence, which is dynamic and offers
direct access, in a way that is efficient in both execution time of access operations (i.e., constant time) and memory “footprint” (i.e., constant factor overhead)
1 October 2020 OSU CSE 15

Dynamic Can Support Fast Sequential Access
• If we want a dynamic collection, then we should give up on storing all entries of the collection in contiguous memory locations
• If we want fast sequential access, then we should give up on fast direct access
– Instead, for every entry in the collection, wherever it is in memory, simply keep a reference to (i.e., memory location of) the “next” entry
1 October 2020 OSU CSE 16

Example: Stack2 Client’s view of a Stack:
this = <13, 6, 18> Implementer’s view of a Stack2:
data data
next next
1 October 2020

Example: Stack2
This is called a singly-
linked-list data structure. Implementer’s view of a Stack2:
Client’s view of a Stack: this = <13, 6, 18>
data data data
next next next
1 October 2020
OSU CSE 18

Example: Stack2
The abstraction function
Client’s view of a Stack: this = <13, 6, 18>
(correspondence) …
Implementer’s view of a Stack2:
data data data
1 October 2020

Example: S
are shown here.
Client’s view of a Stack: this = <13, 6, 18>
Implementer’s view of a Stack2:
ce variables
(fields) of the data representation for Stack2
data data
next next
1 October 2020

The Stack methods only Example: Stack2
require access to the first entry, i.e., the top, so we
Client’s view of a Stack: this = <13, 6, 18>
Implementer’s view of a Stack2:
keep a reference to its node.
data data
next next
1 October 2020

The Stack methods include Example: Stack2
length, so we keep this direct
Client’s view of a Stack:
count of the number of nodes in
this = <13, 6, 18> Implementer’s view of a Stack2:
the linked list.
data data
next next
1 October 2020

Example: Stack2
variables) is called a node in this
this = <13, 6, 18 Each of these objects (a pair of Client’s view of a Stack: singly-linked-list data structure: a reference to the “next” node. variable of type T, and Implementer’s view of a Stack2: data data data next next OSU CSE 1 October 2020 Declaration of Node Class • A Node class is declared as a nested class inside the kernel implementation that uses it in a data representation (e.g., Stack2, Queue2, and similar classes) private final class Node { private T data; private Node next; } 1 October 2020 OSU CSE 24 This declaration is recursive, and Declaration of Node Class • ANodeclassisdeclar may seem circular! One of the instance variables of a e. class inside the kernel implementation that uses it in a data representation (e.g., Stack2, Queue2, and similar classes) private final class Node { private T data; private Node next; } 1 October 2020 OSU CSE 25 How can this work? Declaration of Node Class variable next is a reference variable, hence is a reference to It works because the instance “nested” object. red as a nested class inside the kernel implementation that uses it in a data representation (e.g., Stack2, Queue2, and similar classes) private final class Node { private T data; private Node next; } 1 October 2020 OSU CSE Example: Queue2 this = <9, 21>
rear length
data data
next next
1 October 2020

Example: Queue2 this = <9, 21>
rear length
data data
next next
The abstraction function (correspondence) …
1 October 2020

Example: Queue2 this = <9, 21>
rear length
data data data
next next next
Why do we have this “extra” node (we’ll call it a smart node)?
1 October 2020
OSU CSE 29

Example: Queue2 this = <9, 21>
rear length
data data data
next next next
Why do we have two references into the linked data structure for Queue, but only one for Stack?
1 October 2020
OSU CSE 30

Example: dequeue for Queue2
public final T dequeue() { Node p = this.preFront; Node q = p.next;
T result = q.data; this.preFront = q; this.length–;
return result; }
1 October 2020 OSU CSE 31

Example: dequeue for Queue2 this = <9, 21>
rear length
data data
next next
The abstraction function (correspondence) …
1 October 2020

Node p = this.preFront; Node q = p.next;
Example: dequeue for Queue2
this = <9, 21>
T result = q.data; this.preFront = q; this.length–; return result;
data data data
rear length
1 October 2020

Node p = this.preFront; Node q = p.next;
Example: dequeue for Queue2
this = <9, 21>
T result = q.data; this.preFront = q; this.length–; return result;
data data data
rear length
1 October 2020
pq OSU CSE

Node p = this.preFront; Node q = p.next;
Example: dequeue for Queue2
this = <9, 21>
T result = q.data;
this.preFront = q; this.length–; return result;
rear length
data data
next next
1 October 2020

Example: dequeue for Queue2
this = <9, 21>
Node p = this.preFront; Node q = p.next;
T result = q.data;
this.preFront = q; this.length–; return result;
data data
next next
1 October 2020

Example: dequeue for Queue2 this = <9, 21>
data data data next next next
1 October 2020
the role of the smart node!
Note that this node now plays

Node p = this.preFront; Node q = p.next;
Example: dequeue for Queue2
this = <9, 21>
T result = q.data; this.preFront = q; this.length–; return result;
data data
next next
1 October 2020

Node p = this.preFront; Node q = p.next;
Example: dequeue for Queue2
this = <21> preFront
T result = q.data; this.preFront = q; this.length–; return result;
data data
next next
1 October 2020

Example: dequeue for Queue2 this = <21>
data data data
1 October 2020

Example: dequeue for Queue2 this = <21>
data data data next next next
With local variable p out of scope, this node becomes “garbage”.
1 October 2020
OSU CSE 41

Example: dequeue for Queue2 this = <21>
data data
next next
The abstraction function (correspondence) …
1 October 2020

Example: enqueue for Queue2
public final void enqueue(T x) { Node p = new Node();
Node q = this.rear;
p.data = x;
p.next = null; q.next = p; this.rear = p; this.length++;
1 October 2020
OSU CSE 43

Example: enqueue for Queue2 this = <21>, x = 74
The abstraction function (correspondence) …
1 October 2020

Node p = new Node(); Node q = this.rear;
Example: enqueue for Queue2
p.data = x;
1>, x = 74
q.next = p; this.rear = p; this.length++;
data data
next next
1 October 2020

Example: enqueue for Queue2 reference type in Java is
An instance variable of a
this = <21>, x = 74
always initialized to null;
but it is a good idea to be explicit (see later line of code).
data data
next next
1 October 2020

Node p = new Node(); Node q = this.rear;
Example: enqueue for Queue2
p.data = x;
1>, x = 74
q.next = p; this.rear = p; this.length++;
data data
next next
1 October 2020

Node p = new Node(); Node q = this.rear;
Example: enqueue for Queue2
p.data = x;
1>, x = 74
l this.rear = p;
q.next = p;
this.length++; preFront
data data
next next
1 October 2020

Node p = new Node(); Node q = this.rear;
Example: enqueue for Queue2
p.data = x;
1>, x = 74
q.next = p; this.rear = p; this.length++;
data data
next next
1 October 2020

Example: enqueue for Queue2 this = <21, 74>, x = 74
data data
next next
The abstraction function (correspondence) …
1 October 2020

The “Smart” Node
• To see why we want the extra node at the beginning of the linked list, write the code
for enqueue without it (but be careful) – You should be able to see why it’s a smart
node rather than a dummy node 😄😄
• Why is the smart node helpful in the
representation of a Queue, but not of a Stack?
1 October 2020 OSU CSE 54

Resources • Wikipedia:LinkedDataStructure
– http://en.wikipedia.org/wiki/Linked_data_structure
• BigJava(4thed),Sections15.1,15.2(butnot the part about iterators)
– https://library.ohio-state.edu/record=b8540788~S7
1 October 2020 OSU CSE 55

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts