Linked List

Why?

Data in Array is stored contiguously (in memory locations that are near each other), whereas in Linked list is stored non contiguously (could be near, could be far away from each other in memory).

Vs Array which you have to shift when add() or remove(), add() or remove() is constant for data in the middle of list because elements need not be shifted. The search for the position itself is not constant on average.

Insertion of new element

tmp = new ListNode();

tmp.element = x;

tmp.next = current.next;

current.next = tmp;

Removal of an element

Assume current is one position behind the element that we want to remove

current.next = current.next.next

How to count element in linked list?

1. return integer count
2. create listSize() implementation

public static int listSize (List theList)
{
int size = 0;
ListItr itr = new ListItr (theList);
for (itr.first(); itr.isInList(); itr.advance())
{
size++;
}
return size;
}

Standard

insert(x), remove(x), find(x)

Derived Methods

removeNext(), isInList()

Analisa Kompleksitas Running Time
 insert next, prepend – O(1)
 delete next, delete first – O(1)
 find – O(n)
 retrieve current position – O(1)

Adv

1. growable
2. linear time read, insert, delete

disadv

1. new Node()
2. one reference overhead for each and every node

Print linked list

1. Loop without iterator
2. Recursion without iterator
3. Recursion
4. with Iterator

 

More specific implementation of linked list.

1. Sorted Linked List
   1. insert(x) method is different and not linear since it finds the correct position for the element first before inserting
   2. Could be implemented using inheritance of the previously defined linked list
2. Doubly Linked List
   1. Node has two references (prev and next) instead of just next.
   2. Remove could be different
      1. if current.next and current.prev is not null
      2. current.prev.next = current.next
      3. current.next.prev = current.prev
      4. else if current.next = null
      5. current.prev.next = null
      6. current.prev = null
      7. else if current.prev = null
      8. current.next.prev = null
      9. current.next = null
3. Circular Linked List
   1. Last node has reference to the first node
   2. could be implemented with or without header node.
   3. Insert
      1. 1 newNode = new DoublyLinkedListNode(x);
         2 newNode.prev = current;
         3 newNode.next = current.next;
         4 newNode.prev.next = newNode;
         5 newNode.next.prev = newNode;
         6 current = newNode;
   4. deleteCurrent
      1. 1. current.prev.next = current.next;
         2. current.next.prev = current.prev;
         3. current = current.prev;