Data structure notes

LinkedList

Singly linked.

  Node 1         Node 2         Node 3         Node 4

+-------+      +-------+      +-------+      +-------+

|  Data | ---> |  Data | ---> |  Data | ---> |  Data |

+-------+      +-------+      +-------+      +-------+

| Next  |      | Next  |      | Next  |      | Next  | --> NULL

+-------+      +-------+      +-------+      +-------+

Doubly linked.

           Node 1         Node 2         Node 3         Node 4

         +-------+      +-------+      +-------+      +-------+

  NULL <--|  Data | <--> |  Data | <--> |  Data | <--> |  Data | --> NULL

         +-------+      +-------+      +-------+      +-------+

            Prev            Prev            Prev            Prev

            Next            Next            Next            Next

SearchFirst, Last, Mid

AddFirst, Last, Mid

Update/Delete First, Last, Mid

Queue

Head: enqueue, insert at the first.

Tail: dequeue, remove the last.

Deque

ref. to a Queue, deque offers two ends, where may operate enqueue and dequeue.   

Trees:

A tree consists of nodes and edges. 

A node may follow many other nodes, it is also a nonlinear data structure.

node: elements stored within a tree.

edge: linkages between nodes.

root: a node without parents. 

sibling:  a node having parents, and child. 

leaves: a node having parents, but no children. 

level: the number of edges, from root to leaf.  

 

Heap:

min. heap: child > parent

max heap: child < parent

Add: a. insert next available space. b. trickle up (swap) 

Delete: always remove the root, then replace it with the last child, and then trickle down (swap with the larger child).