Linked Data Structures II: Doubly-Linked Lists
1 October 2020 OSU CSE 1
Sequential Access
Copyright By PowCoder代写 加微信 powcoder
• 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代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com