4.1.3 Comparison of List Implementations Now that you have seen two substantiall

ID: 3814486 • Letter: 4

Question

4.1.3 Comparison of List Implementations Now that you have seen two substantially different implementations for lists, it is natural to ask which is better. In particular, if you must implement a list for some task, which implementation should you choose? Array-based lists have the disadvantage that their size must be predetermined before the array can be allocated. Array-based lists cannot grow beyond their predetermined size Whenever the list contains only a few elements, a substantial amount of space might be tied up in a largely empty array. Linked lists have the advantage that they only need space for the objects actually on the list. There is no limit to the number of elements on a linked list, as long as there is free-store Loc 1649 of 7820 21%

Explanation / Answer

Linked lists need extra storage to store the pointers to next elements. We also cannot access any element randomly as we don't know where in the memory a particular node of the linked list exists. We need help of those pointers to traverse the linked list Linked lists should be helpful when you don't know the size of incoming input.

Here's some Java code that will help you understand linked lists

public class SinglyLinkedList {
private int length;
private Node head;

// Node is a block with data and pointer to the next element
// every node will point to next node, so there will be wastage of pointers
   private class Node {
       int data;
       Node next;

       public Node(int data) {
           this.data = data;
       }
   }

   // initialize the linked list
   public SinglyLinkedList() {
       head = null;
       length = 0;
   }

// O(n) time to find length
   // print the length of the linked list
   public int ListLength() {
       return this.length;
   }

// O(n) time to print the linked list
   // print the linked list
   public void printLinkedList() {
       if (head == null)
           return;
       System.out.println("Linked list: ");

/*
------ ----- -----
| 1 |---> | 2 |--->| 3 |---
------ ----- ----- null

temp ->

currently temp is equal to head
temp will move while printing the data till it becomes null

*/
   Node temp = head;
       while (temp != null) {
           System.out.print(temp.data + " -> ");
           temp = temp.next;
       }
   }

// I have taken some methods as synchronized, because those will be thread safe
// Search on Google for threadsafe to know more about this
// O(1) time to insert at the beginning
   public synchronized void insertAtTheBeginning(int data) {
       Node oldHead = head;
       head = new Node(data);
       head.next = oldHead;
       length++;
   }

// O(n) time if we are inserting at the end of a singly linked list
// because we need to traverse till the end of the linked list
   public synchronized void insertAtTheEnd(int data) {
       if (head == null) {
       // if head is null, inserting at the end is nothing different than inserting at the beginning
// so called insertAtTheBeginning() method
           insertAtTheBeginning(data);
           return;
       }

Node temp = head;
Node newnode = new Node(data);

       while (temp.next != null)
           // go to the end of the linked list
           temp = temp.next;
       temp.next = newnode;
       length++;
   }

// O(n) time to insert at the middle/end, and O(1) time to insert at the beginning
   public synchronized void insertAtThePosition(int position, int data)
           throws Exception {
       if (position < 0)
           position = 0;
       if (position > length)
           position = length;
       if (position == 0) {
           insertAtTheBeginning(data);
           return;
       }

Node temp = head;
Node newNode = new Node(data);

       for (int i = 1; i < position; i++) {
           temp = temp.next;
       }
       newNode.next = temp.next;
       temp.next = newNode;
       length++;
   }

// O(1) time to delete one element
   public synchronized void deleteFromTheBeginning() {
       Node temp = head;
       if (head != null) {
           head = temp.next;
           temp = null;
       }
       length--;
   }

// O(n) time to delete from the end, as we need to traverse the whole linked list
   public synchronized void deleteFromTheEnd() {
       if (head == null)
           return;
       if (head.next == null) {
           head = null;
           return;
       }
       Node p = head, q = null;
       while (p.next != null) {
           q = p;
           p = p.next;
       }
       p = null;
       q.next = null; // to prevent loitering
       length--;
   }

// O(n) time to delete from the middle/end, and O(1) time to delete from the beginning
   public synchronized void deleteFromThePosition(int position) {
       if (position < 0)
           position = 0;
       if (head == null)
           return;
       if (position >= length)
           return;
       if (position == 0) {
           deleteFromTheBeginning();
           return;
       }

       Node p = head, q = null;
       int k = 0;
       while (p.next != null && k < position) {
           q = p;
           p = p.next;
           k++;
       }
       q.next = p.next;
       p = null;
       length--;
   }

   public static void main(String args[]) throws Exception {
// created a linked list

       SinglyLinkedList lld = new SinglyLinkedList();

       lld.insertAtTheBeginning(3);
       lld.insertAtTheBeginning(2);
       lld.insertAtTheBeginning(1);
       lld.insertAtTheEnd(4);

       lld.insertAtThePosition(0, 5);
       lld.deleteFromTheBeginning();
       lld.deleteFromTheEnd();
       lld.deleteFromTheEnd();
       lld.deleteFromTheEnd();
       lld.deleteFromThePosition(1);

lld.printLinkedList();
}
}

Array based lists (i.e Dynamic Arrays eg. ArrayList)
I am explaining dynamic arrays with the help of dynamically expanding stack.
We can access element randomly. Because system knows the base address of the array. If we want to access fifth element, we can just use the formula (base address + (size of integer) * 5) to access the fifth element.
We should use dynamic arrays if the data size is predictable and doesn't get reduced or increased often.

public class ResizingArrays {
public int top = 0;
private String[] stack = new String[1]; // initial size of the array is 1

   public void push(String item) {
// if array's length is equal to top (i.e. if top of the stack is equal to length of the array)
// resize the array (here we are doubling the size)
       if (stack.length == top)
           resize(stack.length * 2);
       stack[top++] = item;
   }

// if the array is 25% full, cut it into half to avoid wastage of space
   public String pop() {
       if (top > 0 && top == stack.length / 4)
           resize(stack.length / 2);
       String item = stack[top];
       stack[top--] = null;
       return item;
   }

// O(1) time to get the top of the array
   public boolean isEmpty() {
       return top == 0;
   }

// O(n) space to copy the whole array in new array of double the size
   public void resize(int capacity) {
       String copy[] = new String[capacity];
       for (int i = 0; i < capacity; i++)
           copy[i] = stack[i];
       stack = copy;
   }

   public static void main(String args[]) throws Exception {
       ResizingArrays sos = new ResizingArrays();
       sos.push("one");
       sos.push("two");
       sos.push("three");
       sos.push("four");
       System.out.println(sos.pop());
       System.out.println(sos.pop());
       System.out.println(sos.pop());
       System.out.println(sos.pop());
       System.out.println(sos.pop());
   }

}