0% found this document useful (0 votes)

20 views62 pages

Arrays, Linked Lists and Recursion: Algorithms and Data Structures COMP3506 / 7505

Q: What is the role of memory location pointers in managing a linked list's head, tail, and current size?

Memory location pointers in a linked list manage references to the head and tail nodes of the list, which are used to access the start and end of the list efficiently. The head pointer leads to the first node, while the tail points to the last node, facilitating quick insertions at both ends. The current size is tracked by an integer variable, adjusting as nodes are added or removed, aiding in operations that require the list's length .

Q: Explain the difference between linear, binary, and multiple recursion. Provide examples of suitable problems for each recursion type.

Linear recursion involves making a single recursive call within each recursion depth, effectively creating a linear chain of calls. An example problem is computing the factorial of a number. Binary recursion, on the other hand, involves two recursive calls for each step, often exemplifying a divide and conquer scenario, such as calculating Fibonacci numbers or performing a binary tree traversal. Multiple recursion allows for several recursive calls within each step, used in problems like finding all subsets of a set, where choices at each step lead to multiple subsequent choices .

Q: How would you implement a recursive algorithm in Java to find all subsets of a set, and what type of recursion does this represent?

To implement a recursive algorithm to find all subsets of a set in Java, deploy a method that builds subsets incrementally. The main recursive call would include or exclude each element at the current index and recursively process remaining elements. This represents multiple recursion, as each element results in multiple recursive paths, creating a tree of subset possibilities. This approach would enumerate all possible combinations, leveraging recursion's ability to manage branching paths efficiently .

Q: Explain how recursive algorithms pass results back to the calling context, using the 'ReverseArray' function as an example.

Recursive algorithms pass results back through return values of the recursive function calls, swiftly compiling the results upon reaching the base case. In the 'ReverseArray' function, the swapping of elements is carried out at each recursive call, so no explicit values need to be returned immediately. Instead, the completion of swaps as recursion 'unfolds' progressively alters the original array, thereby reflecting the reversed state by the time the initial call returns .

Q: What strategies do binary recursion methods use to solve problems, and why are they particularly suitable for divide-and-conquer approaches?

Binary recursion methods employ strategies that split the problem into two smaller subproblems, solving each recursively before combining results. This method works well for divide-and-conquer because it reduces the problem size at every step, making recursive calculations more manageable and efficient. The example of the binary sum method ('BinarySum') illustrates dividing an array into halves until reaching base cases and summing results to achieve the final solution .

Q: How can a recursive method elicit the base case and ensure progress towards it? Illustrate with an example provided in the sources.

A recursive method should first test for one or more base cases, ensuring that recursion eventually terminates. For instance, in the example 'public void recursiveMethod(int n)', recursion stops when n is less than or equal to 0. The recursive calls make progress towards this base case by either reducing n by 1 or dividing it by 2, depending on whether n is odd or even .

Q: How does tail recursion differ from linear recursion in terms of computational efficiency and conversion potential to iterative structures?

Tail recursion is a form of linear recursion where the recursive call is the last operation performed before returning a result. This structure makes tail recursion more efficient due to the potential for tail call optimization by the compiler. It can be easily converted into an iterative form, which generally uses constant stack space, unlike non-tail recursive functions that require additional stack frames for each recursive call .

Q: What are the primary advantages of using linked lists over arrays, and in what scenarios would a linked list be preferred?

Linked lists offer dynamic size adjustment without needing to copy or resize the data structure, as with arrays. They provide fast insertion and deletion at the head and tail thanks to direct pointer manipulation. Linked lists are preferred in scenarios where frequent insertions and deletions from the list head or tail are necessary, whereas arrays are optimal for fast indexed access .

Q: Describe the recursive approach to reversing an array and how it contrasts with an iterative approach.

The recursive approach to reversing an array involves swapping the elements at mirrored indices and then recursively calling the function on the subarray excluding these two indices. The recursion terminates when the indices cross. This approach uses additional stack space due to recursive calls, unlike the iterative approach, where a simple loop can execute the swaps with a single pass and constant space complexity .

Q: What is the purpose of the 'addFirst' method in a linked list implementation, and how does it affect the structure of the list?

The 'addFirst' method aims to insert a new node at the beginning of a linked list. It adjusts the 'next' pointer of the new node to point to the current head of the list, then sets this node as the new head. If the list was previously empty, it also sets the tail to this node. This operation ensures that the list size is incremented, reflecting the addition of the new node .

The document discusses arrays and linked lists. Arrays have constant time access to indexed elements but fixed size, while linked lists have dynamic and incremental growth but slower access times. Sample code in Java demonstrates creating and adding elements to arrays and linked lists.

Uploaded by

jimmy

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

20 views62 pages

Arrays, Linked Lists and Recursion: Algorithms and Data Structures COMP3506 / 7505

Uploaded by

jimmy

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Arrays, Linked Lists and

Recursion
Algorithms and Data Structures

COMP3506 / 7505
Arrays
• Data structure consisting of a group of elements
having a single name that are accessed by
indexing.
– computer science definition of an array
• Occupies a contiguous area of storage.
– most programming languages
• Each element has the same data type.
– statically typed programming languages
Java Example 1
1 public class Example1
2 {
3 public static void main(String[] args)
4 {
5 int[] array = new int[4];
6 array[0] = 255;
7 }
8 }
Java Example 1
1 public class Example1
2 {
3 public static void main(String[] args)
4 {
5 int[] array = new int[4];
6 array[0] = 255;
7 }
8 }
Java Example 1
1 public class Example1
2 {
3 public static void main(String[] args)
4 {
5 int[] array = new int[4];
6 array[0] = 255;
7 }
8 }
Java Example 1
1 public class Example1
2 {
3 public static void main(String[] args)
4 {
5 int[] array = new int[4];
6 array[0] = 255;
7 }
8 }
Java Example 1
1 public class Example1
2 {
3 public static void main(String[] args)
4 {
5 int[] array = new int[4];
6 array[0] = 255;
7 }
8 }
Java Example 2
1 public class Example2
2 {
3 public static void main(String[] args)
4 {
5 String[] array = new String[4];
6 array[0] = new String("Hello world");
7 [Link](array[0]);
8 }
9 }
Java Example 2
1 public class Example2
2 {
3 public static void main(String[] args)
4 {
5 String[] array = new String[4];
6 array[0] = new String("Hello world");
7 [Link](array[0]);
8 }
9 }
Java Example 2
1 public class Example2
2 {
3 public static void main(String[] args)
4 {
5 String[] array = new String[4];
6 array[0] = new String("Hello world");
7 [Link](array[0]);
8 }
9 }
Java Example 2
1 public class Example2
2 {
3 public static void main(String[] args)
4 {
5 String[] array = new String[4];
6 array[0] = new String("Hello world");
7 [Link](array[0]);
8 }
9 }
Java Example 2
1 public class Example2
2 {
3 public static void main(String[] args)
4 {
5 String[] array = new String[4];
6 array[0] = new String("Hello world");
7 [Link](array[0]);
8 }
9 }
Java Example 2
1 public class Example2
2 {
3 public static void main(String[] args)
4 {
5 String[] array = new String[4];
6 array[0] = new String("Hello world");
7 [Link](array[0]);
8 }
9 }
Java Example 3
1 public class Array
2 {
3 private Object[] data;
4
5 public Array()
6 {
7 [Link] = new Object[4];
8 }
9
10 public static void main(String[] args)
11 {
12 Array arrayObject = new Array();
13 }
14 }
Java Example 3
1 public class Array
2 {
3 private Object[] data;
4
5 public Array()
6 {
7 [Link] = new Object[4];
8 }
9
10 public static void main(String[] args)
11 {
12 Array arrayObject = new Array();
13 }
14 }
Java Example 3
1 public class Array
2 {
3 private Object[] data;
4
5 public Array()
6 {
7 [Link] = new Object[4];
8 } arrayObject: null
9
10 public static void main(String[] args)
11 {
12 Array arrayObject = new Array();
13 }
14 }
Java Example 3
1 public class Array
2 {
3 private Object[] data;
4
5 public Array()
6 {
7 [Link] = new Object[4];
8 } arrayObject: null
9
10 public static void main(String[] args)
11 {
12 Array arrayObject = new Array();
13 }
14 }
Java Example 3
1 public class Array
2 {
3 private Object[] data;
4
5 public Array()
6 {
7 [Link] = new Object[4];
8 } arrayObject: null
9
10 public static void main(String[] args)
11 {
12 Array arrayObject = new Array();
13 }
14 }
Java Example 3
1 public class Array
2 {
3 private Object[] data;
4
5 public Array()
6 {
7 [Link] = new Object[4];
8 } arrayObject: null
9
10 public static void main(String[] args)
11 {
12 Array arrayObject = new Array();
13 }
14 }
Java Example 3
1 public class Array
2 {
3 private Object[] data;
4
5 public Array()
6 {
7 [Link] = new Object[4];
8 } arrayObject: 0xFFFC
9
10 public static void main(String[] args)
11 {
12 Array arrayObject = new Array();
13 }
14 }
Contiguous Uniform Storage
• What does it get us?

• What does it cost us?

Arrays (insert)
Arrays (insert)
Arrays (insert)
Arrays (insert)
Arrays (insert)
Arrays (insert)
Arrays (insert)
Arrays (insert)
Arrays Summary
• Pros
– Constant time access to indexed memory location
• Cons
– Fixed size
• Resizing requires copying all existing values to new
array
– Sorted insert
• Best case constant
• Worst case, must shuffle entire array of n elements.
Linked Lists

• Dynamic
– Heap provides a dynamic supply of memory for
new objects.

• Incremental
– Chained data structure is used to allow incremental
growth.
LinkedList and ListNode
class ListNode<T> {
T element;
ListNode<T> next;
}

public class LinkedList<T> {

private ListNode<T> head;
private ListNode<T> tail;
private int size;

…
}
LinkedList (addFirst)
public class LinkedList<T> {
private ListNode<T> head;
private ListNode<T> tail;
private int size;

public void addFirst(ListNode<T> aNode) {

[Link] = [Link];
[Link] = aNode;

if ([Link] == null) {
[Link] = aNode;
}
[Link]++;
}
}
Java Example 4
1 public class Example4
2 {
3 public static void main(String[] args)
4 {
5 LinkedList<Integer> list = new LinkedList();
6 ListNode<Integer> node = new ListNode();
7
8 [Link] = 11;
9
10 [Link](node);
11 }
12 }
Java Example 4
1 public class Example4 0x0000
Program Code
2 { …
3 public static void main(String[] args) … Java Stack
4 {
…
5 LinkedList<Integer> list = new LinkedList();
…
6 ListNode<Integer> node = new ListNode();
7 …
8 [Link] = 11; …
9 …
10 [Link](node); …
11 } Free Memory
…
12 } …
…
…
…
…
0xFFFC Memory Heap
Java Example 4
1 public class Example4 0x0000
Program Code
2 { …
3 public static void main(String[] args) … main():
4 {
… PC: 5
5 LinkedList<Integer> list = new LinkedList();
… list: null
6 ListNode<Integer> node = new ListNode();
7 … node: null
8 [Link] = 11; …
9 …
10 [Link](node); …
11 } …
12 } … Free Memory
…
…
…
…
0xFFFC Memory Heap
Java Example 4
1 public class Example4 0x0000
Program Code
2 { …
3 public static void main(String[] args) … main():
4 {
… PC: 6
5 LinkedList<Integer> list = new LinkedList();
… list: 0xFFF4
6 ListNode<Integer> node = new ListNode();
7 … node: null
8 [Link] = 11; …
9 …
10 [Link](node); …
11 } … Free Memory
12 } …
list: …
LinkedList …
head 0xFFF4 head: null
tail 0xFFF8 tail: null
size: 0 0xFFFC size: 0
Java Example 4
1 public class Example4 0x0000
2 { Program Code
…
3 public static void main(String[] args) … main():
4 {
… PC: 8
5 LinkedList<Integer> list = new LinkedList();
… list: 0xFFF4
6 ListNode<Integer> node = new ListNode();
7 … node: 0xFFEC
8 [Link] = 11; …
9 …
10 [Link](node); … Free Memory
11 } …
12 }
…
list: 0xFFEC element: null
LinkedList node:
ListNode 0xFFF0 next: null
head 0xFFF4 head: null
element
tail 0xFFF8 tail: null
next
size: 0 0xFFFC size: 0
Java Example 4
1 public class Example4 0x0000
2 { Program Code
…
3 public static void main(String[] args) … main():
4 {
… PC: 10
5 LinkedList<Integer> list = new LinkedList();
… list: 0xFFF4
6 ListNode<Integer> node = new ListNode();
7 … node: 0xFFEC
8 [Link] = 11; …
9 …
Free Memory
10 [Link](node); …
11 } …
12 }
0xFFE8 11
list: 0xFFEC element: 0xFFE8
LinkedList node:
ListNode element: 0xFFF0 next: null
head Integer 0xFFF4 head: null
element
tail value: 11 0xFFF8 tail: null
next
size: 0 0xFFFC size: 0
Java Example 4 0x0000
Program Code
1 public class LinkedList<T> { …
2 private ListNode<T> head; … main():
3 private ListNode<T> tail;
… PC: 10
4 private int size;
… list: 0xFFF4
5
6 public void addFirst(ListNode<T> aNode) { … node: 0xFFEC
7 [Link] = [Link]; … addFirst():
8 [Link] = aNode; … PC: 7
9
… this: 0xFFF4
10 if ([Link] == null) {
… aNode: 0xFFEC
11 [Link] = aNode;
12 } Free Memory
13 [Link]++; 0xFFE8 11
14 list:} 0xFFEC element: 0xFFE8
15LinkedList
} node: 0xFFF0
element: next: null
ListNode
head Integer 0xFFF4 head: null
element
tail value: 11 0xFFF8 tail: null
next
size: 0 0xFFFC size: 0
Java Example 4 0x0000
Program Code
1 public class LinkedList<T> { …
2 private ListNode<T> head; … main():
3 private ListNode<T> tail;
… PC: 10
4 private int size;
5 … list: 0xFFF4
6 public void addFirst(ListNode<T> aNode) { … node: 0xFFEC
7 [Link] = [Link]; … addFirst():
8 [Link] = aNode; … PC: 8
9
… this: 0xFFF4
10 if ([Link] == null) {
… aNode: 0xFFEC
11 [Link] = aNode;
12 } Free Memory
13 [Link]++; 0xFFE8 11
14 list:} 0xFFEC element: 0xFFE8
15LinkedList
} node:
element: 0xFFF0 next: null
ListNode
head Integer 0xFFF4 head: null
element
tail value: 11 0xFFF8 tail: null
next
size: 0 0xFFFC size: 0
Java Example 4 0x0000
Program Code
1 public class LinkedList<T> { …
2 private ListNode<T> head; … main():
3 private ListNode<T> tail;
… PC: 10
4 private int size;
5 … list: 0xFFF4
6 public void addFirst(ListNode<T> aNode) { … node: 0xFFEC
7 [Link] = [Link]; … addFirst():
8 [Link] = aNode; … PC: 10
9
… this: 0xFFF4
10 if ([Link] == null) {
… aNode: 0xFFEC
11 [Link] = aNode;
12 } Free Memory
13 [Link]++; 0xFFE8 11
14 list:} 0xFFEC element: 0xFFE8
15LinkedList
} node:
element: 0xFFF0 next: null
ListNode
head Integer 0xFFF4 head: 0xFFEC
element
tail value: 11 0xFFF8 tail: null
next
size: 0 0xFFFC size: 0
Java Example 4 0x0000
Program Code
1 public class LinkedList<T> { …
2 private ListNode<T> head; … main():
3 private ListNode<T> tail;
… PC: 10
4 private int size;
5 … list: 0xFFF4
6 public void addFirst(ListNode<T> aNode) { … node: 0xFFEC
7 [Link] = [Link]; … addFirst():
8 [Link] = aNode; … PC: 11
9
… this: 0xFFF4
10 if ([Link] == null) {
… aNode: 0xFFEC
11 [Link] = aNode;
12 } Free Memory
13 [Link]++; 0xFFE8 11
14 list:} 0xFFEC element: 0xFFE8
15LinkedList
} node:
element: 0xFFF0 next: null
ListNode
head Integer 0xFFF4 head: 0xFFEC
element
tail value: 11 0xFFF8 tail: null
next
size: 0 0xFFFC size: 0
Java Example 4 0x0000
Program Code
1 public class LinkedList<T> { …
2 private ListNode<T> head; … main():
3 private ListNode<T> tail;
… PC: 10
4 private int size;
5 … list: 0xFFF4
6 public void addFirst(ListNode<T> aNode) { … node: 0xFFEC
7 [Link] = [Link]; … addFirst():
8 [Link] = aNode; … PC: 13
9
… this: 0xFFF4
10 if ([Link] == null) {
… aNode: 0xFFEC
11 [Link] = aNode;
12 } Free Memory
13 [Link]++; 0xFFE8 11
14 list:} 0xFFEC element: 0xFFE8
15LinkedList
} node:
element: 0xFFF0 next: null
ListNode
head Integer 0xFFF4 head: 0xFFEC
element
tail value: 11 0xFFF8 tail: 0xFFEC
next
size: 0 0xFFFC size: 0
Java Example 4 0x0000
Program Code
1 public class LinkedList<T> { …
2 private ListNode<T> head; … main():
3 private ListNode<T> tail;
… PC: 10
4 private int size;
5 … list: 0xFFF4
6 public void addFirst(ListNode<T> aNode) { … node: 0xFFEC
7 [Link] = [Link]; … addFirst():
8 [Link] = aNode; … PC: 14
9
… this: 0xFFF4
10 if ([Link] == null) {
… aNode: 0xFFEC
11 [Link] = aNode;
12 } Free Memory
13 [Link]++; 0xFFE8 11
14 list:} 0xFFEC element: 0xFFE8
15LinkedList
} node:
element: 0xFFF0 next: null
ListNode
head Integer 0xFFF4 head: 0xFFEC
element
tail value: 11 0xFFF8 tail: 0xFFEC
next
size: 1 0xFFFC size: 1
Java Example 4
1 public class Example4 0x0000
2 { Program Code
…
3 public static void main(String[] args) … main():
4 {
… PC: 10
5 LinkedList<Integer> list = new LinkedList();
… list: 0xFFF4
6 ListNode<Integer> node = new ListNode();
7 … node: 0xFFEC
8 [Link] = 11; …
9 …
Free Memory
10 [Link](node); …
11 } …
12 }
0xFFE8 11
list: 0xFFEC element: 0xFFE8
LinkedList node:
ListNode element: 0xFFF0 next: null
head Integer 0xFFF4 head: 0xFFEC
element
tail value: 11 0xFFF8 tail: 0xFFEC
next
0
size: 1 0xFFFC size: 1
Linked Lists Summary
• Do not allow access via index
– Must traverse entire list
• Singly linked lists
– Can easily add to head and tail of list
– Can easily remove from head of list
• Doubly linked lists
– Can add to/remove from head and tail
– Can insert anywhere you have a pointer to
Recursion
• Linear Recursion

• Binary Recursion

• Multiple Recursion
Recursion Pattern

• Recursion: when a method calls itself

• Classic example – the factorial function:
– n! = 1 * 2 * 3 * 4 * ... * (n-1) * n

• Recursive definition:  1 if n = 0
f (n) = 
n  f ( n − 1) else

Adapted from: © 2004 Goodrich & Tamassia, updated 2005, 2018

Linear Recursion

• Test for base cases

– Begin by testing for a set of base cases
• there should be at least one
– Every possible chain of recursive calls must
eventually reach a base case
– Handling of each base case should not use
recursion

Adapted from: © 2004 Goodrich & Tamassia, updated 2005, 2018

Linear Recursion
• Perform a single recursive call
• Define each possible recursive call so that it
makes progress towards a base case
public void recursiveMethod(int n) {
if (n <= 0) {
return 0;
} else if (n%2 == 0) {
return 1 + recursiveMethod(n/2);
} else {
return 1 + recursiveMethod(n-1);
}
}

Adapted from: © 2004 Goodrich & Tamassia, updated 2005, 2018

Example: ReverseArray
• ReverseArray(A, i, j)

public void ReverseArray(int[] A, int i, int j) {

if (i < j) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
ReverseArray(A, i+1, j-1);
}
}

Adapted from: © 2004 Goodrich & Tamassia, updated 2005, 2018

Example: ReverseArray

8 1

Adapted from: © 2004 Goodrich & Tamassia, updated 2005, 2018

Defining Arguments for Recursion

• Recursive methods often need different

arguments than non-recursive approaches
• Recursive methods may require additional
parameters
• We defined array reversal as
ReverseArray(A, i, j) not ReverseArray(A)
Why?
Defining Arguments for Recursion

• Operands are passed forward via parameters

• Simple case
– result of recursion is passed back via return
• In other cases
– Target object is also passed as parameter
– Results of recursive calls may
• affect target object
• be passed back via return
Tail Recursion
• Tail recursion occurs when a linearly recursive
method makes its recursive call as its last step
• Easily converted into iterative forms

public void ReverseArray( int[] A, int i, int j ) {

if ( i < j ) { public void ReverseArray2( int[] A, int i, int j ) {
int tmp = A[ i ]; while ( i < j ) {
A[ i ] = A[ j ];
A[ j ] = tmp; int tmp = A[ i ];
A[ i ] = A[ j ];
ReverseArray( A, i + 1, j - 1 ); A[ j ] = tmp;
}
} i += 1; j -= 1;
}
}
Adapted from: © 2004 Goodrich & Tamassia, updated 2005, 2018
Binary Recursion
• Binary recursion occurs whenever there are
two calls for each non-base case
public int BinarySum(int[] A, int i, int len) {
if (len == 1) {
return A[i];
} else {
return BinarySum(A, i, len/2)
+ BinarySum(A, i + len/2, len/2);
}
}

Binary Recursion

Multiple Recursion

• Multiple recursion makes potentially many

recursive calls
– not just one or two
• Multiple recursion is a way of enumerating all
possible combinations of a set of elements

Recursion Summary

• Linear Recursion
– Tail Recursion can easily be mapped to iterative
algorithms
• Binary Recursion
– Recursive method contains two recursive calls
(divide and conquer)
• Multiple Recursion
Lecture Summary

• Arrays
– Fast access, slow to increase size (requires copy)
• Linked lists
– Fast access to head and tail, slow random access
• Recursion
Feel Like Programming?
• Write a recursive algorithm that will output all the
subsets of a set of n elements (without repeating
subsets)
• Describe a recursive algorithm that will check if an
array A of integers contains an integer A[i] that is the
sum of two integers that appear earlier in A, that is,
such that A[i] = A[j] + A[k] for j, k < i such that j != k

• Implement them in Java!

Common questions