Scribd
Upload
6 views34 pages

Understanding List Data Structures

data structure lab note

Uploaded by

양산일
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views34 pages

Understanding List Data Structures

data structure lab note

Uploaded by

양산일
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structure

Lists, Stacks, and Queues (Chapter 4)

U Kang
Seoul National University

U Kang 1
In This Lecture
 Learn the List data structure

 Compare the array-based and link-based


implementation of List in terms of time and space

 Understand the motivation and the main idea of


freelist

U Kang 2
Lists
 A list is a finite, ordered sequence of data items.

 Important concept: List elements have a position.

 Notation: <a0, a1, …, an-1>

 What operations should we implement?

U Kang 3
List Implementation Concepts
 Our list implementation will support the concept
of a current position.

 Operations will act relative to the current position.

<20, 23 | 12, 15>

U Kang 4
List ADT
public interface List<E> {
public void clear();
public void insert(E item);
public void append(E item);
public E remove();
public void moveToStart();
public void moveToEnd();
public void prev();
public void next();
public int length();
public int currPos();
public void moveToPos(int pos);
public E getValue();
}
U Kang 5
List ADT Examples
 List: <12 | 32, 15>
[Link](99);

Result: <12 | 99, 32, 15>

 Iterate through the whole list:


for ([Link](); [Link]()<[Link]();
[Link]()) {
it = [Link]();
doSomething(it);
}
U Kang 6
List Find Function
/** @return True if k is in list L,
false otherwise */
public static boolean
find(List<Integer> L, int k) {
for ([Link]();
[Link]()<[Link](); [Link]())
if (k == [Link]()) return true;
return false; // k not found
}

U Kang 7
Array-Based List Insert

U Kang 8
Array-Based List Class (1)
class AList<E> implements List<E> {
private static final int defaultSize = 10;

private int maxSize;


private int listSize;
private int curr;
private E[] listArray;

// Constructors
AList() { this(defaultSize); }
AList(int size) {
maxSize = size;
listSize = curr = 0;
listArray = (E[])new Object[size];
}
U Kang 9
Array-Based List Class (2)
public void clear()
{ listSize = curr = 0; }
public void moveToStart() { curr = 0; }
public void moveToEnd() { curr = listSize; }
public void prev() { if (curr != 0) curr--; }
public void next()
{ if (curr < listSize) curr++; }
public int length() { return listSize; }
public int currPos() { return curr; }

U Kang 10
Array-Based List Class (3)
public void moveToPos(int pos) {
assert (pos>=0) && (pos<=listSize) :
"Position out of range";
curr = pos;
}

public E getValue() {
assert (curr >= 0) && (curr < listSize) :
"No current element";
return listArray[curr];
}

U Kang 11
Insert
/** Insert "it" at current position */
public void insert(E it) {
assert listSize < maxSize :
"List capacity exceeded";
for (int i=listSize; i>curr; i--)
listArray[i] = listArray[i-1];
listArray[curr] = it;
listSize++;
}

U Kang 12
Append
public void append(E it) { // Append "it"
assert listSize < maxSize :
"List capacity exceeded";
listArray[listSize++] = it;
}

U Kang 13
Remove
/** Remove and return the current element */
public E remove() {
if ((curr < 0) || (curr >= listSize))
return null;
E it = listArray[curr];
for(int i=curr; i<listSize-1; i++)
listArray[i] = listArray[i+1];
listSize--;
return it;
}

U Kang 14
Array Based List

 Strengths?

 Weaknesses?

U Kang 15
Link Class
 Dynamic allocation of new list elements.
class Link<E> {
private E element;
private Link<E> next;

// Constructors
Link(E it, Link<E> nextval)
{ element = it; next = nextval; }
Link(Link<E> nextval) { next = nextval; }

Link<E> next() { return next; }


Link<E> setNext(Link<E> nextval)
{ return next = nextval; }
E element() { return element; }
E setElement(E it) { return element = it; }
} U Kang 16
Linked List Position (1)
Naïve Method Insert 10 at the current position

U Kang 17
Linked List Position (2)
Improved Method Insert 10 at the current position

U Kang 18
Linked List Class (1)
class LList<E> implements List<E> {
private Link<E> head;
private Link<E> tail;
protected Link<E> curr;
int cnt;

//Constructors
LList(int size) { this(); }
LList() {
curr = tail = head = new Link<E>(null);
cnt = 0;
}

U Kang 19
Linked List Class (2)
public void clear() {
curr = tail = head = new Link<E>(null);
cnt = 0;
}
public void moveToStart() { curr = head; }
public void moveToEnd() { curr = tail; }
public int length() { return cnt; }
public void next() {
if (curr != tail) { curr = [Link](); }
}
public E getValue() {
assert [Link]() != null :
"Nothing to get";
return [Link]().element();
}
U Kang 20
Insertion

U Kang 21
Insert/Append
// Insert "it" at current position
public void insert(E it) {
[Link](new Link<E>(it, [Link]()));
if (tail == curr) tail = [Link]();
cnt++;
}
public void append(E it) {
tail = [Link](new Link<E>(it, null));
cnt++;
}

U Kang 22
Removal

U Kang 23
Remove
/** Remove and return current element */
public E remove() {
if ([Link]() == null) return null;
E it = [Link]().element();
if (tail == [Link]()) tail = curr;
[Link]([Link]().next());
cnt--;
return it;
}

U Kang 24
Prev
/** Move curr one step left;
no change if already at front */
public void prev() {
if (curr == head) return;
Link<E> temp = head;
// March down list until we find the
// previous element
while ([Link]() != curr)
temp = [Link]();
curr = temp;
}

U Kang 25
Get/Set Position
/** Return position of the current element */
public int currPos() {
Link<E> temp = head;
int i;
for (i=0; curr != temp; i++)
temp = [Link]();
return i;
}
/** Move down list to "pos" position */
public void moveToPos(int pos) {
assert (pos>=0) && (pos<=cnt) :
"Position out of range";
curr = head;
for(int i=0; i<pos; i++)
curr = [Link]();
}
U Kang 26
Comparison of Implementations

Array Based List Linked List

Insertion and
Deletion
Prev / access to an
element
Pre-allocate space

Additional space
overhead

U Kang 27
Space Comparison
 When should we use array, rather than linked list,
to minimize space?
 “Break-even” point:

DE = n(P + E);
n = DE
P+E

D: Number of maximum elements in array.


n: Number of elements in linked list
E: Space for data value.
P: Space for pointer.
U Kang 28
Freelists

System new and garbage collection are slow.


 Add freelist support to the Link class.
 When releasing an object, insert the object at the head of the
freelist
 When allocating an object, get it from the head of the
freelist

U Kang 29
Link Class Extensions
static Link freelist = null;
static <E> Link<E> get(E it, Link<E> nextval) {
if (freelist == null)
return new Link<E>(it, nextval);
Link<E> temp = freelist;
freelist = [Link]();
[Link](it);
[Link](nextval);
return temp;
}
void release() { // Return to freelist
element = null;
next = freelist;
freelist = this;
}
U Kang 30
Not Using Freelist
public void insert(E it) {
[Link](new Link<E>(it, [Link]()));
if (tail == curr) tail = [Link]();
cnt++;
}
public E remove() {
if ([Link]() == null) return null;
E it = [Link]().element();
if (tail == [Link]()) tail = curr;
[Link]([Link]().next());
cnt--;
return it;
}

U Kang 31
Using Freelist
public void insert(E it) {
[Link]([Link](it, [Link]()));
if (tail == curr) tail = [Link]();
cnt++;
}
public E remove() {
if ([Link]() == null) return null;
E it = [Link]().element();
if (tail == [Link]()) tail = curr;
Link<E> tempptr = [Link]();
[Link]([Link]().next());
[Link]();
cnt--;
return it;
}
U Kang 32
What You Need to Know
 ADT of the List data structure and when it is
needed

 Comparison of the array-based and link-based


implementations of List in terms of time and
space

 The motivation and the main idea of freelist

U Kang 33
Questions?

U Kang 34

You might also like