Week 4

Structures (struct) provide a way to unify several variables of different types into a single, new variable type which can be assigned its own type name.

On Singly linked lists

Singly linked list’s node contains two items:

• Data,
• and a pointer to the next node (if exists).

Once a linked list is created, it’s a good idea to always keep track of the first element of the list since it’s in knowing list’s first element, that othe members can be known following the pointers each member’s node contains.

In inserting a new element to a linked list, it is generally better to insert at the start of the list.

When inserting:

• allocate space for the new element,
• set its pointer value to point to the old “list head”,
• move the list head pointer from old head to new head.

NOTE: It is very important to point from new head to old head before making the newly inserted element head of the list to prevent “orphaning” the entire list.

When deleting an entire linked list from memory, start freeing from the end of the list to the head. If done the other way around, the list’s head goes first and there wouldn’t be any way to reference the rest of the list resulting in a memory leak.

Deleting a single element from a singly linked list is kind of tricky. It would involve moving back and forth the chain to “reconnect” the list. Unfortunately, a singly linked list’s node only contains a pointer to the next element, not the previous one. See doubly linked lists.

On Hashtables

Hashtables sort of combines an array with a linked list. It combines the random access ability of an array with the dynamism of a linked list. A couple pointers:

• Hashtables (HT for short)are suited for situations where we don’t care if the data is sorted.

• HTs contain:

  • a hash function
  • an array

• A good hash function should:

  • use only the data being hashed
  • use all of the data being hashed
  • be deterministic (when, say, “Kizito” is passed, it should alway return the same output at any given time)
  • uniformly distribute data
  • generate very different hashes for very similar data

• Great hash functions can be gotten off the internet – Always cite your sources, though.

• Hashtables are prone to experiencing “collision"s and while linear probing could be a convinient fix for the short term, it too is subject to a problem known as “clustering”.

• “Chaining” could be a possible resolution to collisions, though.

Some Other Data Structures

• TRIES => combines structures an pointers
• Stack => A Last In First Out (LIFO) structure which supports two primary operations: Push & Pop
• Queue => A First In First Out (FIFO) structure which supports two primary operations: Enqueue & Dequeue

Comparing Some Data Structures

Arrays:

• insertion is bad
• deletion is bad
• lookup is great O(1)
• fixed size
• relatively easy to sort
• small, size-wise

Linked Lists:

• easy insertion
• easy deletion (esp doubly linked lists)
• bad lookup O(n)
• difficult to sort
• small, size-wise (bigger than array, though)

Hash Tables:

• insertion is two-step: hash, then sort
• easy deletion
• faster lookup than Linked Lists
• not ideal if sorting is the goal

Tries:

• O(1) insertion
• fast lookup O(1)
• easy deletion O(1)
• always sorted
• huge size

Other bullets from D. Malan’s lecture

• Stack => “shortterm” memory.
• Heap => “longterm” memory (still non-persistent, though).
• malloc allocates memory in the heap.