# Linked data structures

### Algoritmi ricorsivi

Esempio, la binary search può essere anche implementata in modo ricorsivo:

```java
/**
 * Search in the array A in positions numbered loIndex to hiIndex, inclusive,
 * for the specified value. If the value is found, return the index in the array
 * where it occurs. If the value is not found, return -1. Precondition: The
 * array must be sorted into increasing order.
 */

static int binarySearch(int[] A, int loIndex, int hiIndex, int value) {
	if (loIndex > hiIndex) {
		// The starting position comes after the final index,
		// so there are actually no elements in the specified
		// range. The value does not occur in this empty list!
		return -1;
	} else {
		// Look at the middle position in the list. If the
		// value occurs at that position, return that position.
		// Otherwise, search recursively in either the first
		// half or the second half of the list.
		int middle = (loIndex + hiIndex) / 2;
		if (value == A[middle])
			return middle;
		else if (value < A[middle])
			return binarySearch(A, loIndex, middle - 1, value);
		else // value must be > A[middle]
			return binarySearch(A, middle + 1, hiIndex, value);
	}
} // end binarySearch()

```

### Linked data structures

Struttura dati definita in modo ricorsivo:

```java
class Node {
  String item;
  Node next;  
}
```

![](https://3264574854-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVU7WiFKajQhwsnAlGh%2F-L_lGbuSXaG77rbDPh7H%2F-L_lJ0KpuhzY2nnLxR5p%2Flinked_list.PNG?alt=media\&token=a5edb8a4-d315-4f27-9185-1b0cefbd7191)

![Esempio di linked list ](https://3264574854-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVU7WiFKajQhwsnAlGh%2F-L_lGbuSXaG77rbDPh7H%2F-L_lJHLBbn2mQQlFjlQa%2Flinked_list2.PNG?alt=media\&token=10d580ec-74e0-4887-b506-c5b92db30872)

![](https://3264574854-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVU7WiFKajQhwsnAlGh%2F-L_lGbuSXaG77rbDPh7H%2F-L_lJVwTpuISJmSHpfgP%2Flinked_list_inserting.PNG?alt=media\&token=fa0f9063-fbe1-44fd-ad14-ff7afcb507ad)

### Alberi binari

```java
class TreeNode {
    int item; // The data in this node.
    TreeNode left; // Pointer to the left subtree.
    TreeNode right; // Pointer to the right subtree.
}
```

![Struttura ad albero](https://3264574854-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVU7WiFKajQhwsnAlGh%2F-L_lKPqNLK_gcWuyeUnK%2F-L_lKsFolsXl3tYbJDRG%2Falbero.PNG?alt=media\&token=7b5bf596-6341-4e67-be29-eabce949440e)

![](https://3264574854-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVU7WiFKajQhwsnAlGh%2F-LaPMJO1ztheZbNXAPWt%2F-LaPMT0O0-NCDOrIBtlc%2Falbero_ordinato.PNG?alt=media\&token=69610d89-5c4f-4db1-bf23-8eb2b0d51a0c)