Linked Lists vs Arrays

Linked List

Methods you need to know:

• addAtHead
• addAtTail
• insertInOrder
• delete
• print
• isEmpty
• isFull(?)

Notes:

1. The insertInOrder method can be a little tricky. The best way to tackle it is to consider the following four possibilities:
   1. list is empty
   2. new node needs to go at the head of the list
   3. new node needs to go at the tail of the list
   4. new node needs to go somewhere in the middle of the list
2. The isFull method is confusing. If a linked list is “full” it means you’ve run out of memory! I guess it could mean that you impose an artificial limit on the number of nodes.

Google site:

• Methods in Java
• Methods in pseudocode
• Methods as flowcharts
• Diagrams
• Explanatory notes
• Advantages and disadvantages (in your own words)

Advantages and disadvantages:

Adv: Doesn’t waste memory. A linked list only uses as much memory as it needs, since new nodes are created and deleted as necessary.

Adv: Easy to insert in the middle of a linked list. Because nodes are not contiguous in memory and they use object references to “point” to the next logical node, it is easy to insert items in the middle of the list by changing the object references.

Disadv: Doesn’t support direct access. With a singly-linked list, the only point of access is the reference HEAD, which points to the first node. It is not possible to jump into the middle of the list. You have to start at the head and loop through the list sequentially. Looking up values in large lists could be slow for this reason.

Arrays

Methods you need to know:

• add
• delete

Notes:

These methods could mean adding and deleting anywhere within the array, so you need to know those algorithms about shifting everything up one (for add) or shifting everything down one (for delete).

Google site:

• Methods in Java
• Methods in pseudocode
• Methods as flowcharts
• Diagrams
• Explanatory notes
• Advantages and disadvantages (in your own words)

Advantages and disadvantages:

Adv: Supports direct access. Easy to access the middle elements of an array by using the index, e.g. arry[25] accesses the 26th element.

Adv: Simple to use. Built in to the language (in the case of Java).

Disadv: An array’s size is set when it is declared. This leads to two possible problems:

• If it is too big, then unused elements constitute a waste of memory.
• If it is too small then it has to be recreated and elements of the old array have to be copied to the new array. This is an expensive operation because it takes time.

Disadv: Array elements are physically next to each other in RAM. This means that it is difficult to insert data into the middle of an array. It’s a bit like trying to sit in among a group of people at the cinema. You can’t just “insert” a new seat, people have to get up and move.