Data Structures

This is a series of notes about the book Programming Interview Exposes

Linked Lists

There are three types of Linked List:

• Singly Linked Lists (generally called only Linked Lists)
• Double Linked Lists
• Circular Linked Lists

Description Each data element in the list has a link (a pointer or reference) to the next element that follows in the list. The last element in such a list is called the tail of the list and has an empty or null link.

Trees and Graphs

A tree is made up of nodes with zero, one o several references or pointers to other nodes. Each node has only one other node referencing it.

Binary trees

In a binary tree, each node has no more than two children, referred to as left and right.

Binary Search Tree

The most common way to store ordered data in a tree is to use a special tree called a binary search tree (BST). In a BST, the value held by a node's left child is less than or equal to its own value, and the value held by a node's right child is greater than or equal to its value. In effect, the data in a BST is sorted by value.

Graphs

Graphs are more general and more complex than trees. Like trees, they consist of nodes with children—a tree is actually a special case of a graph. But unlike tree nodes, graph nodes (or vertices) can have multiple “parents,” possibly creating a loop (a cycle).