Alright, so imagine you have an array. In this array, you’re going to constantly be adding elements periodically. You set the array to an initial size of 10,000 elements, only to realize you need 25,000 weeks later. This is a problem, and one that can be solved rather easily.

You see, arrays are statically sized – the only way to make an array larger is to create a new array with open space, and then join the two together with the new array to the right. Fortunately, there’s a much easier solution! Enter the LinkedList.

Imagine you want to store loads and loads of integer data, but don’t know how much space you’ll need down the line. Well, you can take this approach:

class Link{

    int data;
    Link next;

}

Do you see what’s going on here? No? Well, let’s dive in. We have a class here that has two data members. One, is an object that is of type Link – aka the same class. The next element is the data itself. Now, what happens here is that we create an initial Link as such:

Link initial = new Link(1);

Now, what we have is one element of our array, if you will. Except its NOT AN ARRAY! It’s a Link to our LinkedList! It looks like this:

{1, null}

So where does the `null` point to? Well no where for now. But what it can do is point to the next Link in the List! See what I did there? Now we can just add Links to our chain freely, without worrying about memory. This is a powerful thing, as it allows us to create open ended arrays. Let’s fix our class to add data to this LinkedList.

class Link{

    int data;
    Link next;

    public static void addLink(int data){
        
        // we create the new link here
        Link newLink = new Link(data);

        // afterwards, we create a new Link 'n'
        // and make it equal to the current object
        // Which is the start of the chain of course!
        Link n = this;

        // iterate through the chain, until the next
        // object is a null (aka, empty)
        while(n.next != null){
            n = n.next;
        }

        // and then we set that empty object to our new Link!
        n.next = newLink;

    }

}

If you don’t understand it at first, draw it out and read the comments! You’ll understand. Alright, so now let’s deal with deleting a Link. Well, that’s easy! When we iterate through the Link’s, we check to see if the currentLink.next is equal to the one we want to delete. If  it is, we set our current Link’s next reference to the Link AFTER the one we want gone. Think of a chain!

{Current Link} – > {Link we want to delete} -> {Some other Link}

If we want to delete the second Link, we just make the current Link point all the way to the last one, effectively removing the second Link from our chain! Let’s see that in code:

Link deleteLink(Link initial, int data){

    Link n = initial;
    
    // if the current link holds the data
    // that you want to delete, return that
    // Link's NEXT Link
    if(n.data == data){
        return initial.next;
    }

    // iterate through and check to see if we 
    // can find the Link we want deleted.
    // If we find it, remove that link
    // from the chain!
    while(n.next != null){

        if(n.next.data == data){
            n.next = n.next.next;
            return n;
        }
        n = n.next;
    }

   return head;
}

And that right there, is how easy to is to add and delete Link’s from a LinkedList! We even implemented it from scratch. I hope something is dead clear now.

A data structure is ANY structured data. We created one just now, and it so happens to already be a defined one. However, you can create ANY data structure you’d like to fit your current problem by creating your own class to manage it. This is of key importance. In Java, this is how everything is implemented – classes. And that right there, is a glimpse of what Object Oriented Programming allows us to do.

Alright, so now that we know what a LinkedList is and how to build one, let’s solve a problem. This one is from ‘Cracking the Coding Interview’.

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the Ts digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE
Input:(7-> 1 -> 6) + (5 -> 9 -> 2).Thatis,617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem. EXAMPLE
Input:(6 -> 1 -> 7) + (2 -> 9 -> 5).Thatis,617 + 295.
Output: 9 -> 1 -> 2.That is, 912.

And here is how we could go about solving that:

 

static int addLinks(Link one, Link two){

    // this will hold the first integer value
    int value1 = 0;

    // this will hold the second integer value
    int value2 = 0;

    // this will be our multiplication factor.
    // In essence, we use this to fill in the number
    // slots (i.e. 10's, 100's, 1000's, etc...)
    int factor = 1;

    // iterate through the first LinkedList
    // to generate the first integer
    while(one != null){
        value1 = value1 + (one.data * factor);
        factor *= 10;
        one = one.next;
    }
    
    // reset the factor
    factor = 1;
  
    // iterate through the second LinkedList
    // to generate the second integer
    while(two != null) {
        value2 = value2 + (two.data * factor);
        factor *= 10;
        two = two.next;
    }
   
    // return the summed values of both! 
    return value1 + value2;
}

And that’s all there is to LinkedLists! In part 3, we’re going to be using them to create Stacks and Queues. See you there!

Advertisements