-1
$\begingroup$

Note its not a homework question, just practice Hi i have always seen linked list implementation in java using the following piece of code

class Node
     {
         int key;
         Node prev;
         Node next;
     }

I implemented linked list using single array which could be increased as per need. (Took code of increasing array from Effective Java book). Please tell me why the above method is preferred over my implementation. According to me it should occupy less memory. Rest i would really like to use an optimized code. And please forgive me if my question is trivial. I am new to algorithms.

public class LinkedListImplementation {

private int list[];
private int currentSize;

public LinkedListImplementation() {
    this.list = new int[20];
    currentSize = 0;

}

void printList() {
    if (currentSize == 0) {
        System.out.println("******************Empty List********************");
        return;
    }
    System.out.println("*************Printing list***************");
    for (int i = 0; i < currentSize; i++) {
        System.out.print(list[i] + " ");
    }
    System.out.println();
}

int head() {
    if (currentSize == 0) {
        System.out.println("******************Empty List********************");
        return -1;
    }
    return 0;
}

int next(int i) {
    if (i >= currentSize || i < 0) {
        System.out.println("*********************Invalid************************");
        return -1;
    } else if (i == (currentSize - 1)) {
        System.out.println("***********Reached the end of list***************");
        return -1;
    }
    return i + 1;
}

int previous(int i) {
    if (i >= currentSize || i < 0) {
        System.out.println("*********************Invalid************************");
        return -1;
    } else if (i == 0) {
        System.out.println("***********Reached the head of list***************");
        return -1;
    }
    return i - 1;
}

int listSearch(int k) {
    int x = head();
    while (x != -1 && list[x] != k) {
        x = next(x);
    }
    return x;
}

private void ensureCapacity() {

    if (list.length <= currentSize) {

        list = Arrays.copyOf(list, 2 * list.length + 1);
    }
}

void listInsertBack(int x) {
    currentSize++;
    ensureCapacity();

    list[currentSize - 1] = x;

}

void listInsertFront(int x) {
    currentSize++;
    ensureCapacity();
    int i = currentSize - 1;
    while (i != 0) {
        list[i] = list[i - 1];
        i--;

    }
    list[0] = x;

}

public static void main(String args[]) {
    LinkedListImplementation lli = new LinkedListImplementation();
    lli.printList();
    lli.listInsertBack(10);
    lli.printList();
    lli.listInsertFront(20);
    Random rand = new Random();
    int count = 0;
    while (count != 30) {
        lli.listInsertBack(rand.nextInt(50));
        count++;
    }

    lli.printList();
    Scanner scn=new Scanner(System.in);
    System.out.println("Enter the number to be searched\n");
    System.out.println(lli.listSearch(scn.nextInt()));
}

}

$\endgroup$

closed as off-topic by D.W., Wandering Logic, FrankW, Juho, Rick Decker Jun 9 '14 at 16:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – D.W., Wandering Logic, FrankW, Juho, Rick Decker
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Hello, and welcome to Computer Science StackExchange! Most questions about programming and actual programs are better suited to StackOverflow, our sister site. Please feel free to ask questions here as they relate to mathematical, scientific and computational aspects of programs. Thanks for your understanding, and again, welcome! $\endgroup$ – Patrick87 Jun 9 '14 at 17:17
  • $\begingroup$ Hi thank you. Ill keep in mind. How to remove it from here now? $\endgroup$ – jasleen Jun 9 '14 at 23:58
2
$\begingroup$

This should really be on StackOverflow, not Computer Science, but here's an answer anyway.

There are a few points. First of all, your code is not a linked list. You created an unbounded array, an array that grows dynamically (good implementations also shrink dynamically, but that is beyond the scope of this question). A linked list is defined (more or less) as in the first implementation: each node stores some data and points to the node after it (and sometimes behind it, in the case of a doubly-linked list). They are two different data structures.

Now, onto the question of efficiency. From your code, it seems you are interested in the operations insertAtBack, insertAtFront, and search. Both arrays and lists support search in $O(n)$ time, though arrays can support search in $O(\log n)$ if they are sorted, whereas linked lists cannot. Linked lists have $O(1)$ time insertAtBack and insertAtFront operations. While insertAtBack is $O(n)$ worst-case for unbounded arrays, it is actually amortized $O(1)$, so it's not that bad. However, insertAtFront is $O(n)$ under any measure of time complexity.

So, in short, a linked-list is what you want in this situation (though linked lists are rarely used on their own, and almost always used as a building block of other data structures).

As for your question of space, you're right in that the linked-list is less efficient, as it needs to store two pointers for every data entry. On the other hand, linked-lists have the advantage that each node can be stored in a separate location in memory, whereas arrays are stored in a contiguous block of memory, which can be bad if the array is really large.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.