- An DList's size variable is always correct.
- There is always a tail node whose next reference is null.
public class ListNode {
public int item;
public ListNode next;
}
public ListNode(int i, ListNode n) {
item = i;
next = n;
}
public ListNode(int i) {
this(i, null);
}public class SList {
private SListNode head; // First node in list.
private int size; // Number of items in list.
public SList() { // Here's how to represent an empty list.
head = null;
size = 0;
}
public void insertFront(Object item) {
head = new SListNode(item, head);
size++;
}
}
- Insertion: O(1)
- Deletion: O(1)
- Indexing: O(n)
- Searching: O(n)
- An DList's size variable is always correct.
- There is always a tail node whose next reference is null.
- item.next and item.previous either points to an item or null (if tail or head).
public class ListNode {
public int item;
public ListNode next;
}
public ListNode(int i, ListNode n) {
item = i;
next = n;
}
public ListNode(int i) {
this(i, null);
}public class SList {
private DListNode head; // First node in list.
private int size; // Number of items in list.
public DList() { // Here's how to represent an empty list.
head = null;
tail = null;
size = 0;
}
public void insertFront(Object item) {
head = new SListNode(item, head);
size++;
}
public void insertBack(Object item) {
tail = new SListNode(item, head);
size++;
}
}- Insertion: O(1)
- Deletion: O(1)
- Indexing: O(n)
- Searching: O(n)
- n is the number of keys (words).
- N buckets exists in a table.
- n ≤ N << possible keys.
- Load Factor is n/N < 1 (Around 0.75 is ideal).
Compression Function:
- h(hashCode) = hashCode mod N.
- Better: h(hashCode) = ((a * (hashCode) + b) mod p) mod N
- p is prime >> N, a & b are arbitrary positive ints.
- Really Large Prime: 16908799
- If hashCode % N is negative, add N.
| insert(key, value) | find(key) | remove(key) |
|---|---|---|
| Compute the key's hash code and compress it to determine the entry's bucket. | Hash the key to determine its bucket. | Hash the key to determine its bucket. |
| Insert the entry (key and value together) into that bucket's list. | Search the list for an entry with the given key. | Search the list for an entry with the given key. |
| If found, return the entry; else, return null. | Remove it from the list if found. | |
| Return the entry or null. |