Lesson 3 Array and Linked List

Array

Ordered Array

Definition of Ordered Array

an array of consecutive elements with ordered values

insert of Ordered Array

“cut in “ from the back

consecutive: head + tail

for(i=tail;i>=0;i--){
    if(arr[i]>data)
        arr[i+1] = arr[i];
    else{
        arr[i] = data;
        break;
        }
}

construct of Ordered Array

insertion sort: construct with multiple insert

example: 1, 3, 7, 4, 6, 5, 2
Two methods:

• getMinIndex multiple times(selection sort)
• insert multiple times (insertion sort)

update and remove of Ordered Array

• maintenance
  • updateByIndex(index, data): rotate up or down
  • removeByIndex(index): fill in from the back
• ordered array: more maintenance efforts

Binary Search within Ordered Array

Application: Book Search within (Digital) Library

comparable elements: book IDs

• book ID nunmber
• for books on the same shelf, ordered by ID
• Sequential Search Algorithm

for i from 0 to tail
    if (arr[i].ID == toFind.ID)
        return FIND
    end for
    return NOTFIND

• Sequential Search Algorithm with Cut

for i from 0 to tail
    if (arr[i].ID == toFind.ID)
        return FIND
    if(arr[i].ID>toFind.ID) //Cut step
        return NOTFIND
    end for
    return NOTFIND

ordered: possibly easier to declare not found

• Binary Search Algorithm

“cut” multiple times by fast random access to the middle

Binary Search Algorithm:

arr[mid] <=> toFind
arr[mid] > toFind: cut [mid…tail]
arr[mid] < toFind: cut[0…mid]
arr[mid] = toFind: FIND

begin = 0
end = tail
while(left book){
    mid = (begin+end)/2
    arr[mid]>toFind:end = mid-1
    arr[mid]<toFind:begin = mid+1
    arr[mid] = toFind:FIND
}
return NOTFIND

Linked List

Application: Polynomial Computation

example:
%20%3D%205%2Bx%2B4x%5E2%2B10x%5E5%2Bx%5E%7B16%7D#card=math&code=f%28x%29%20%3D%205%2Bx%2B4x%5E2%2B10x%5E5%2Bx%5E%7B16%7D)
%20%3D%203-6x%5E5#card=math&code=g%28x%29%20%3D%203-6x%5E5)
5
1
-4
10
1
: (0,5), (1,1),(2,-4),(5,10),(16,1)
: (0,3),(5,-6)

solution 0: use odered array on (exponent, coefficient)

Issue of (Ordered) Array for Polynomial Computation

ordered (consecutive) array: not flexible for resizing/insertion/removal

Solution 1: Singly Linked List for Flexible Insertion

insert (3,-6) to storage 1126:

overhead of next <=> flexible insertAfter

head
next
Singly Linked List:

insertAfter(node,data)
    newnode = new node(data)
    newnode->next = node->next
    node->next = newnode

Slide:

Singly Linked List as Abstract Data Structure: Access

• access
  • data getAt (node): memory, index address
  • node getHead()
  • getNext(node)
  • insertAfter(node, data)
  • insertHead(data)

linked list: seqential access;
array: random access

Singly linked List as ADT: Maintenance

• maintainance
  • construct(length): trivial
  • updateHere(node,data): trivial
  • removeAfter(node): simple
  • removeHead: simple
    remove:

tofree = node->next
node->next = node->next->next
free(tofree)

dummy head:
set an empty node, its next is head

dommyhead = new node()
dommyhead->next = head

Doubly Linked List

removeHere for Singly Linked List

in Singly Linked List, we can only use removeAfter(node)
removeHere (and insertHere): hard for singly linked list

Doubly Linked List: More Flexible removeHere

can directly locate the node to remove

overhead of prev <=> flexible removeHere

Iterator for Sequential Access

for (node = head;node!=end; node = node->next){
    ...
}
//reverse doubly linked list
for(node = tail; node!= end; node = node->prev){
    ...
}
for(index = 0;indexM=tail;index++){
    ...
}

iterator: abstraction of array index, linked list node and more

C++ STL List: a Doubly Linked List

• access
  • node getHead(): list.begin()
  • node getNext(node): iterator++
  • data getAt(node): (*iterator)
  • insertHere(node, data): list.insert(iterator, data)
    and more
• maintenance
  • updateHere(node, data): (*iterator = data)
  • removeHere(node): list.erase(iterator)
    and more
    STL list and its iterator:
    a more “structured” way of using douly linked list
    more details about iterator: c.biancheng.net/view/338.html
    www.cplusplus.com/reference/iterator/iterator

Application: Sparse Vector in Scientific Computing

“vector”: [0, 3.5, 0, 0, 7, 4.2, 9]
number of dimension * size(double)

skip ‘0’ while storing:
“sparse vector”: (2, 3.5), (5, 7), (6, 4.2), (7, 9)

polynomial: can be viewed as special case of sparse vector

example: