Java Linked List Questions

I开发者_Go百科'm trying to understand how Linked Lists are implemented in Java.

Should I create separate linked list classes for lists and nodes, or can I just call import java.util.LinkedList, or do we need both?

Also, do we need an iterator to print the list?

You've asked several different questions in here. I think I've addressed them all here, so let me know if I've missed something:

1. If your goal is to be a client of a linked list, then you should just use java.util.LinkedList. This is a pre-written, optimized implementation of a linked list that is good for most applications.

2. If your goal is to implement a linked list, then you will at least need to have a class representing a linked list node. Depending on your use case, you may also want to consider making a class that, like LinkedList, encapsulates the list and exports a nice interface around it to simplify common tasks for clients. Typically, you would do this by defining the linked list node type as a nested class inside of the client-facing linked list.

3. You could have a program that uses both a custom linked list class and the LinkedList collection. One use case for this would be to have a program that uses a LinkedList primarily as an implementation of a queue, but uses an exposed, custom linked list for other tasks where it needs to specifically splice lists together or pull individual cells out of the list. For example, if you were implementing a Fibonacci heap, you would likely implement your own linked list even if you were using LinkedList elsewhere in the program. The two aren't mutually exclusive.

4. I'm not sure what you mean by "iterator" in your last question. If you want to print out the contents of a linked list, the best way to do it is to create a reference to the first cell of the linked list and then continuously march it forward until you hit the end of the list. Whether or not you wrap this in a java.util.Iterator object is up to you. It's probably easiest to create an actual Iterator type to do the iteration, since it lets you interface with foreach loops and other APIs that manipulate collections.

Hope this helps!

Do you want to learn how to use java.util.LinkedList or how to build your own custom LinkedList? You don't need to use java.util.LinkedList in order to build (implement) your own LinkedList class.

I use an Iterator when I'm dealing with the standard java.util.LinkedList, not when I'm implementing my own LinkedList class.

Below is a simple implementation of the LinkedList class with the append and print method. My print method does the job of traversing through the LinkedList to display each element.

public class Solution {
    public static void main(String[] args) {
         LinkedList list = new LinkedList();
         list.append(1);
         list.append(2);
         list.append(3);
         list.append(5);
         list.append(4);
         list.append(8);

         list.print(list.head);
    }
}
class Node {
    Node next;
    int data;
    public Node(int d) {
       data = d;
    }
}
class LinkedList {
    Node head;

    public void append(int val) {
       if (head == null) {
          head = new Node(val);
          return;
       }
       Node current = head;
       while (current.next != null) {
          current = current.next;
       }
       current.next = new Node(val);
    }

    public void print(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

Below is an example of using java.util.LinkedList and Iterator.

import java.util.LinkedList;
import java.util.Iterator;

public class Solution {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(4);
        list.add(7);
    }

    public static void print(LinkedList<Integer> list) {
         Iterator it = list.iterator();
         while(it.hasNext()) {
             System.out.print((int)(it.next()) + " ");
         }
    }
}

When using java.util.LinkedList, you could even just print the LinkedList through System.out.println()

import java.util.LinkedList;
import java.util.Iterator;

public class Solution {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(4);
        list.add(7);

        System.out.println(list);
    }
}

In order to create a linked list in java, you need two base classes: -

1. Node Class
2. SinglyLinkedList (Or DoublyLinkedList) Class

You can get a basic implementation of Java Linked List code of these classes and of the main() function class here.