CS代写 CSE 12 – cscodehelp代写

Linked Data Structures II: Doubly-Linked Lists
1 October 2020 OSU CSE 1

Sequential Access

Copyright By cscodehelp代写 加微信 cscodehelp

• Sequential access usually means accessing the entries of a collection (with a string model) in increasing order of
position, by accessing the “next” entry in the collection
• Sometimes you can access the entries sequentially in the reverse direction, too, by accessing the “previous” entry in the collection
– Example: the OSU CSE components List
1 October 2020 OSU CSE 2

Interfaces and Classes
Standard Iterable extends extends
implements
ListKernel
implements
1 October 2020

Interfaces and Classes
Standard Iterable
extends extends Standard has contracts
ListKernel
newInstance
transferFrom
for three methods:
implements
implements
1 October 2020

Interfaces and Classes
ListKernel has contracts for six
addRightFront
removeRightFront
moveToStart
leftLength
rightLength
extends extends
implements
ListKernel
implements
1 October 2020

Interfaces and Classes
has contracts for fiveother
rightFront
moveToFinish
swapRights
extends replaceRightFront extends
implements
ListKernel
implements
1 October 2020

Mathematical Model
LIST_MODEL is ( left: string of T, right: string of T
type ListKernel is modeled by LIST_MODEL
1 October 2020 OSU CSE 7

Mathematical Model
LIST_MODEL is ( left: string of T, right: string of T
type ListKernel is modeled by LIST_MODEL
1 October 2020 OSU CSE 8
You may think of these two strings as being to the left
and right, respectively, of the “current position”.

No-argument Constructor • Ensures:
this = (< >, < >)
1 October 2020 OSU CSE 9

void advance()
• Advances the position in this by one. • Updates:this
• Requires:
this.right /= < >
• Ensures:
this.left * this.right = #this.left * #this.right and
|this.left| = |#this.left| + 1 1 October 2020 OSU CSE

void retreat()
• Retreats the position in this by one. • Updates:this
• Requires:
this.left /= < >
• Ensures:
this.left * this.right = #this.left * #this.right and
|this.left| = |#this.left| – 1 1 October 2020 OSU CSE

What’s New?
• With just advance, sequential access is only to the “next” position
– A singly-linked list representation provides good performance
• Withretreataswellasadvance, sequential access is also to the “previous”
– A singly-linked list representation provides poor performance
1 October 2020 OSU CSE 12

What’s New?
To see why, write an
• With just advance, sequential access is
only to the “next” position
– A singly-linked list representation provides good performance
• Withretreataswellasadvance, sequential access is also to the “previous”
– A singly-linked list representation provides poor performance
1 October 2020 OSU CSE 13
implementation of
retreat using only the
ListKernel methods.

Example: List2 (SLL) this = (<18>, <6>)
data data data next next next
1 October 2020
OSU CSE 14

Example: List2 (SLL) this = (<18>, <6>)
data data data next next next
1 October 2020
The abstraction function (correspondence) …

Example: List2 (SLL) this = (<18>, <6>)
data data data next next next
1 October 2020
OSU CSE 16
The “current position” is indicated by this.lastLeft.

A Second Smart Node
• Note that the code for Queue2 has no special cases at all, but the code for
List2 needs to handle a special case in addRightFront and removeRightFront
• This can be eliminated by introducing a smart node at the end of the singly-linked list, too, so the two smart nodes are like “bookends”
1 October 2020 OSU CSE 17

A Second Smart Node
You should be able to re-write
this code for List2 with two
smart nodes, as illustrated on • Note that the code for Queue2 has no
the next slide. special cases at all, but the code for
List2 needs to handle a special case in addRightFront and removeRightFront
• This can be eliminated by introducing a smart node at the end of the singly-linked list, too, so the two smart nodes are like “bookends”
1 October 2020 OSU CSE 18

Example: SLL “Bookends”
this = (<18>, <6>)
data data data data ?
next next next next
1 October 2020
OSU CSE 19
postFinish

Example: SLL “Bookends”
this = (<18>, <6>)
data data data data
next next next next
There is really no need for a null reference any more; ? here means “unused”.
1 October 2020
OSU CSE 20
postFinish

Doubly-Linked Lists
• In addition to the second smart node, the
code for List3 introduces one other (major) change
• The data structure is now a doubly-linked list, in which there are two references per node: one to the “next” node and one to the “previous” node
– This allows retreat to be implemented efficiently
1 October 2020 OSU CSE 21

Example: List3 (DLL) this = (<18>, <6>)
data data data
lastLeft next next next postFinish ?
prev prev prev
1 October 2020

Resources • Wikipedia:LinkedDataStructure
– http://en.wikipedia.org/wiki/Linked_data_structure
• BigJava(4thed),Section15.2(butnotthepart about iterators)
– https://library.ohio-state.edu/record=b8540788~S7
1 October 2020 OSU CSE 23

程序代写 CS代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com