Different garbage collection algorithms are available:
A Document Object Model (DOM) is a programming interface to represent HTML and XML as a tree structure.
A document consist of nodes. There are different types of nodes, the main ones are:
When we talk about doc documents, we usually talk about reading and writing XML.
Here's a code snipped to create a DOM document, that represents a simple XML:
An hash table is a data structure that stores key-value pair using an hash code as an index.
Insertion and search are close to constant time, and it's even faster than a tree. The downsides are that it uses arrays, which are difficult to expand, and it cannot be easily traversed in order.
Hash tables have to deal with collisions as different keys can produce same hash codes. One approach is to find another empty cell, when this happens. Another approach is to use a linked list for each possible hash code (or array index).
Here's an example of implementation of an hash table:
A tree is a data structure, where data is represented in the form of a hierarchical tree.
Trees can be binary, if nodes can have max two children, or multiway, if they can have more.
A search binary tree is a binary tree used for searches. However, a search binary tree works well only when nodes are balanced, and nodes are balanced when data is inserted randomly.
Red-black tree are binary trees that solve this limitation, by restructuring the tree during insertion and deletion. The name is given by the fact each node is assigned a different colour.
It's a data structure of type binary tree, used for searches. It combines the advantages of an ordered arrays (with quick searches) and a linked lists (with quick insertions and deletions).
Each node of a binary tree has max two children. In addition to this, a search binary tree has each left node with a key less than the parent and each right node with a key greater or equal than the parent.
Here's an example of search binary tree:
/** * Data of a node of a search binary tree */ public class TreeData { private int id; private String name;
Binary search is an algorithm that locates a value in an ordered data set by repeatedly halving the data to smaller sets. This is called "divide and conquer" and can be accomplished either with a simple loop or recursion.
This algorithm is very fast, however the data must have been ordered before.
Here's an example that uses recursion to find the index of a value in an integer array:
/** * Demonstration of a binary search */ public class App { private static int ordArray[] = {2,4,6,9,11,12,15,18,21,24,30,31}; public static void main(String[] args) {
A linked list is a data structure where each item contains a link to the next one and sometimes the previous one.
It's very efficient for deletion, but slow for random access.
Here's an example:
/** * Represents a single item in a linked list */ public class Link { private String data; private Link next; private Link previous; public Link(String data) { this.data = data; } public String getData() { return data; } public void setData(String data) { this.data = data; } public Link getNext() { return next; }
A queue is a first-in-first-out data structure. It works like a queue at a cinema, where the first to queue is the first to enter. However, in a data structure we don't really move forward the items, we move the pointers to the start and the end of the queue. As we use an array, the pointers have to wrap around as they reach the bounds of the array.
Here's an example:
/** * Simple queue */ public class Queue { private int[] array; private int front = 0; private int rear = -1; private int numItems = 0; public Queue(int size) {
A stack is a last-in-last-out data structure. It works like a deck of cards with which we can only add and remove cards from the top.
Here's an example:
/** * Simple stack */ public class Stack { private int[] array; private int top = -1; public Stack(int size) { array = new int[size]; } /** * Adds one element to the top of the stack */ public void push(int i) { if (isFull()) throw new IllegalStateException("push() called on a full stack"); array[++top] = i; } /**
Here are the most common sort algorithms:
Bubble sort: traverses the list and swap contiguous items, if not sorted. It repeats the process until the entire list is sorted.
Selection sort: finds the smallest element and move it at the very left. It repeats the process with the rest of the list, until when fully sorted.
Insertion sort: selects an item and move it to the left of the list. Move another item to the left in the right order compared to the ones already moved. Then it repeats the process until when the list is fully ordered.
Copyright © 2013 Welcome to the website of Davis Fiore. All Rights Reserved.