Hi! I thought to continue the series of data structures articles that have frozen for a while since the recursion post. Welcome back:) As we have finished recursion in a previous article, now we can move to the recursive linking.
First question! What is recursive linking??
If an object has an instance variable of its own class type, we say the object is recursively linked.
If the definition is too complicated to understand at once, let’s take an example. A person can have a child. That child is also a person.
If we put it in to a Class, a Person object has an instance variable called child, where the child is also a Person object.
Eg:
|
1 2 3 |
public class Person { private Person child; //recursive linking } |
See, we have a person inside a person 🙂 The person has a child of the same type Person.
The things get really interesting when there are two or more recursively linked objects in a class.
They will form tree like structures. Here, the things get a little more complicated as well. We will discuss about these trees later on. Today, let’s focus on a single recursively linked variable and the operations associated with them.
Linked Lists
Let’s create another class.
|
1 2 3 4 |
public class Link { String name; Link child; } |
Now, the Link class has a Link variable called child. If we assign an object, that object can again have its own child and this is continued like a list.
We can represent this in a diagram as follows;
This list is actually a list of Strings. Because, the data is stored in the name variable, which is a String. So, if we want to have another type as the list, we can change the variable type.
Now, how do we use this data structure? How to find an item from a list? How to add or remove an item? That is what we are going to discuss next.
Processing the list
Searching
Now, it should be obvious to you that, if we want to search for an item in the list, we have to start from the outermost item and go deeper inside through the child variable. While going inside, we can check if the item we are looking for is available.
Here’s the code for performing the search operation.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public boolean search(String name){ if(this.name.equals(name)) return true; if(this.child==null) return false; else{ Link runner = this.child; while (runner!=null){ if (runner.name.equals(name)) return true; runner=runner.child; } } return false; } |
This is nothing but checking some conditions 🙂 This method is an instance method. That is, we have to create a new Link object first and should call this method through the object.
The first if statement checks whether the first object’s name is the one we are looking for. If so, return true and its job is done. But if the name is different, we have to go deeper inside the linked objects.
Before that, we are checking if there’s an actual list. For that, we use the condition if(this.child==null). If there’s no child, there’s no use of continuing the method so return false and exit.
If the child is not null, we have to traverse the list and check for the first match. In order to do that, first, we create a Link object called runner that points to the child Link object.
We then use a while loop and go from one child to the next by updating the runner, until the runner points to a null reference having no more child Link objects. While moving inside, each time we check if the name of Link object matches the one we need.
It’s easy. Right?
Next. Can you think of methods to add and remove an item from the list???
Adding an item in to the list
Here’s the basic way of adding an item in to our list.
In the example, we have a method to check if one item’s String is larger than the other.
|
1 2 3 4 5 |
public boolean isSmallerThan(Link item2){ //method to compare a Link item with another //Link item called item2 return (this.name.compareTo(item2.name)<0); } |
For example, suppose there are two Link objects called item1 and item2 having names “a” and “b” respectively.
Then, calling item1.isSmallerThan(item2) method will return true (the string method “a”.compareTo(“b”) generates a negative number). So we have the condition that “a” comes before “b” like in a dictionary.
This method is used when adding a new item in to the list. Suppose we have the list in alphabetical order. When adding a new item, we have to make sure the order is preserved. So, we can use this method as a supporter.
Here’s the method of adding an item to the list.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public void insertToListInAscendingOrder(Link item){ Link head = this; //Head is larger than the current item. Skip! if(!head.isSmallerThan(item)){ System.out.println("Skipped! Head is larger than the item to be inserted"); } //Head is smaller than the item. So, go to inner //Link objects, find the proper position and insert the item else{ Link runner = head.child; Link previous = head; while ( runner != null && runner.isSmallerThan(item) ) { previous = runner; runner = runner.child; } item.child = runner; previous.child = item; } } |
This method is also an instance method. So, we must have the Link object list to use this.
There’s a Link object called head. It is the object itself. Head is more like, the starting point of the list. I have added it to make that idea clear.
Let’s see the code. First, we have an if condition. This condition is used to test whether the string stored in the head is larger than the item we are adding. If it larger, what to do? Of course, we have to add the new item before the head. But there’s a problem. What if the head is not the first item in the list? If so, there can be other elements before the head object and we need to go through each of them for the perfect location.
So, I think it is better to implement a separate static method to insert an item before the head.
If the new item is larger than the head, no problem. We can add it to the list. For that, we are again using a while loop and compare each item. Once we find the position, we stop. Here, we have two variables that keep changing continuously. Link objects runner and previous. The runner object points to the next item of the list while previous keeps track of the current item. When we find the place to add the new item, we make runner as the child of the new item and the new item as the child of the current item.
Deleting an item
Removing an item is no more difficult than adding. It just need to follow a similar way. You can easily understand the code if you check it 🙂
|
1 2 3 4 5 6 7 8 9 10 11 |
public void deleteInnterItem(String itemName){ Link runner=this.child; Link prev = this; while (runner!=null && !runner.name.equals(itemName)){ prev = runner; runner = runner.child; } if (runner!=null){ prev.child = runner.child; } } |
That’s all for the recursive linking. Here’s the complete code of the things we have discussed so far. Please note that the code seems to be less robust (I haven’t tested it much. Just needed to give the basic idea) 🙂 There are advanced data structures in Java (maybe you know them already) that are way more easy and attractive to talk about. We are not trying to reinvent the wheel. But I think it’s nice to know the basic logic, how the wheel operates (HOW? :D) Right?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
public class Link { String name; Link child; public boolean search(String name){ if(this.name.equals(name)) return true; if(this.child==null) return this.name.equals(name); else{ Link runner = this.child; while (runner!=null){ if (runner.name.equals(name)) return true; runner=runner.child; } } return false; } public boolean isSmallerThan(Link item2){ //method to compare a Link item with another //Link item called item2 return (this.name.compareTo(item2.name)<0); } public void insertToListInAscendingOrder(Link item){ Link head = this; //Head is larger than the current item. if(!head.isSmallerThan(item)){ System.out.println("Skipped! Head is larger than the item to be inserted"); } //Head is smaller than the item. So, go to inner //Link objects, find the proper position and insert the item else{ Link runner = head.child; Link previous = head; while ( runner != null && runner.isSmallerThan(item) ) { previous = runner; runner = runner.child; } item.child = runner; previous.child = item; } } public void deleteInnterItem(String itemName){ Link runner=this.child; Link prev = this; while (runner!=null && !runner.name.equals(itemName)){ prev = runner; runner = runner.child; } if (runner!=null){ prev.child = runner.child; } } public void printList(){ Link runner = this.child; Link previous = this; System.out.println(previous.name); while (runner!=null){ System.out.println(runner.name); previous = runner; runner = runner.child; } System.out.println(); } public static void main(String[] args){ Link item1 = new Link(); Link item2 = new Link(); Link item3 = new Link(); Link item4 = new Link(); item1.name = "a"; item2.name = "c"; item3.name = "b"; item4.name = "d"; item1.child = item2; item2.child = item4; item1.printList(); item1.insertToListInAscendingOrder(item3); item1.printList(); item1.deleteInnterItem("c"); item1.printList(); System.out.println(item1.search("b")); System.out.println(item1.search("c")); } } |
OUTPUT:
a
c
d
a
b
c
d
a
b
d
true
false
If there’s an error, please be kind to inform me, so I can correct it. Hope this article helped you 🙂 If you like it, please share it among your friends and I really appreciate it!
