A self adjusting list is a list where all insertions are performed at the front

Question

A self adjusting list is a list where all insertions are performed at the front and when an element is accessed by a find, it is moved to the front of the list without changing the relative order of the rest of the list.

(i) write insertion and find algorithms for an array implementation of self adjusting lists.

(ii) write insertion and find algorithms for a linked list implementation of self adjusting lists.

(iii) What are the advantages of such a list over a regular list? Discuss the relative advantages and disadvantages of the array and linked implementations.

Explanation / Answer

i)

insertion algorithm for array

step 1) Dynamically increase array size by memory reallocation.(increase size by 1)

step 2) move ith element to (i+1) th element. arr[i+1] = arr[i].

step 3) read the new value. read tmp.

step 4) store the value at 0 th position in the array. arr[0] = tmp.

step 5) end.

Find algorithm for array

step 1) loop through every element of the list to find target element.

step 2) if the element is found store it in a temporary variable.

step 3) if the location of the target element is x then loop through 0 to x-1.

step 4) move i th element to (i+1)th element.

step 5) end loop

step 6) store target element at first position of the array. arr[0] = tmp and return it.

step 6) end.

ii)

insertion algorithm for linked list

step 1) create a new node and set its value.

step 2) set new node's next pointer point to head's next pointer. (newNode->next = head->next)

step 3) set address of the new node to head. (head = newNode)

step 4) end.

Find algorithm for linked list

step 1)If the value of head node matches the target element then return the head node.

step 2) else declare a previous pointer and iterator pointer.

step 3) make iterator pointer point to next element of head node( iterator = head->next).

step 4) make the previous pointer point to head node( prev = head).

step 5) while iterator->next != NULL iterate.

step 6) if the value of iterator node matches target element then save that node in a temporary node.

step 7) make prev node's next pointer point to iterator node's next element( prev->next = iterator->next).

step 8) iterate from head to target node and point each node's next pointer point to next node's next pointer.

step 9) set head equal to target node which is pointed by a temporary pointer.

step 10) else increment prev and iterator pointer( prev = prev->next and iterator = iterator->next)

step 11) return temporary node( target element).

step 12) end.

iii)

Such self-adjusting list improves performance.

Element lookup becomes fast.

It works like caching mechanism.

Array implementation advantages:

Find operation is relatively easy to implement.

Uses less memory.

Array implementation disadvantages:

Insertion operation is complex. You have to increase the array size dynamically and move all the elements one step further.

Linked list implementation advantages:

Insertion operation is quite trivial and easy to implement.

Insertion operation takes constant time.

the new node can be allocated easily relative to an array.

Linked list implementation disadvantages:

Takes more memory.

Find operation is complex.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.