The elegant recursive solution to a problem is most of the times invaluable. Although the iterative solution of that problem is likely to have a better space and time complexity, it is often preferred to use the recursive version for clarity and simplicity. It is remarkable how easily a problem can be solved by use of a recursive manner. In this article we will try to record a collection of useful recursive functions:
Tag Archive: linked list
The following program reads a set of edges that define a graph and creates a representation of this graph with an adjacency list. The adjacency list of a graph is an array of lists, one for each vertex, where the j-th list contains a linked list of the nodes which are connected with the j-th vertex.
The following program generates N random integers between 0 and 999, creates a linked list inserting a number in each node and then rearranges the nodes of the list so that the numbers appear sorted when we go through the list. For the sorting, it maintains two lists: one input list (not sorted) and one output list (sorted). In each iteration of the loop, it removes a node from the input list and enters it in the appropriate position in the output list. The code is simplified by using head nodes for each list, which contains links to the first node lists. Also, both lists (input and output) are printed.
The function ‘reverse’ in the following example reverses the links in a list, returning a pointer to the end node, which then shows the next of the last node, and so forth, while the link to the first node of the initial list is assigned the value 0 corresponding to null pointer (in C++). To accomplish this task, we must maintain links to three consecutive nodes in the list.
For the representation of individuals arranged in a circle, we create a circular linked list with a combination of each person to the person on his left in the circle. The integer i represents the i-th person in the circle. After you create a circular list of one node for 1, we insert its unique node to nodes 2 to N. We end up with a cycle from 1 to N, with x indicating the node N. Then, starting from 1 we omit M-1 nodes, we define the pointer of the (M-1)-th node to omit the M-th, and continue that way until only one node remains in the list.
This project refers to an Arduino library for implementing a generic, dynamic queue (linked list version).
The data structure is implemented as a class in C++.
For more information, you can get the project itself ‘QueueList‘.
This project refers to an Arduino library implementing a generic, dynamic stack (linked list version).
The data structure is implemented as a class in C++.
For more information, you can get the project itself ‘StackList‘.
Efstathios Chatzikyriakidis 