Creating a LinkedList class from scratch

Question

We were given an assignment to create a LinkedList from scratch, and there are absolutely no readings given to guide us on this migrane-causing task. Also everything online seems to just use Java's built in LinkedList methods and stuff. Anyway, linked lists make perfect sense when using Java's default stuff, but creating it from scratch makes no sense whatsoever. Lets say I have

public class LinkedList {
  private LinkedList next;  
  private final String word;
  // constructor
  public LinkedList(String word, LinkedList next) {
    this.word = word;
    this.next = next;
  }

And thus magically we have a linked list. What is going on? How have I created a linked list like this? How does this work? I'm supposed to write an append method that adds a the given String word parameter to the end of this linkedlist. I tried looking at the addLast built in method for built in java linkedlist class, but it's no help to me, as I really dont understand whats going on. Anyone care to help me out :)

Answer 1

If you're actually building a real system, then yes, you'd typically just use the stuff in the standard library if what you need is available there. That said, don't think of this as a pointless exercise. It's good to understand how things work, and understanding linked lists is an important step towards understanding more complex data structures, many of which don't exist in the standard libraries.

There are some differences between the way you're creating a linked list and the way the Java collections API does it. The Collections API is trying to adhere to a more complicated interface. The Collections API linked list is also a doubly linked list, while you're building a singly linked list. What you're doing is more appropriate for a class assignment.

With your LinkedList class, an instance will always be a list of at least one element. With this kind of setup you'd use null for when you need an empty list.

Think of next as being "the rest of the list". In fact, many similar implementations use the name "tail" instead of "next".

Here's a diagram of a LinkedList containing 3 elements:

Note that it's a LinkedList object pointing to a word ("Hello") and a list of 2 elements. The list of 2 elements has a word ("Stack") and a list of 1 element. That list of 1 element has a word ("Overflow") and an empty list (null). So you can treat next as just another list that happens to be one element shorter.

You may want to add another constructor that just takes a String, and sets next to null. This would be for creating a 1-element list.

To append, you check if next is null. If it is, create a new one element list and set next to that.

next = new LinkedList(word); 

If next isn't null, then append to next instead.

next.append(word); 

This is the recursive approach, which is the least amount of code. You can turn that into an iterative solution which would be more efficient in Java^*, and wouldn't risk a stack overflow with very long lists, but I'm guessing that level of complexity isn't needed for your assignment.

---

^{* Some languages have tail call elimination, which is an optimization that lets the language implementation convert "tail calls" (a call to another function as the very last step before returning) into (effectively) a "goto". This makes such code completely avoid using the stack, which makes it safer (you can't overflow the stack if you don't use the stack) and typically more efficient. Scheme is probably the most well known example of a language with this feature.}

Answer 2

What you have coded is not a LinkedList, at least not one that I recognize. For this assignment, you want to create two classes:

LinkNode
LinkedList

A LinkNode has one member field for the data it contains, and a LinkNode reference to the next LinkNode in the LinkedList. Yes, it's a self referential data structure. A LinkedList just has a special LinkNode reference that refers to the first item in the list.

When you add an item in the LinkedList, you traverse all the LinkNode's until you reach the last one. This LinkNode's next should be null. You then construct a new LinkNode here, set it's value, and add it to the LinkedList.

public class LinkNode { 

    String data;
    LinkNode next;

    public LinkNode(String item) { 

       data = item;

    }

}

public class LinkedList { 

    LinkNode head;

    public LinkedList(String item) { 

       head = new LinkNode(item);

    }

    public void add(String item) { 

       //pseudo code: while next isn't null, walk the list
       //once you reach the end, create a new LinkNode and add the item to it.  Then
       //set the last LinkNode's next to this new LinkNode

    }


}

Answer 3

How about a fully functional implementation of a non-recursive Linked List?

I created this for my Algorithms I class as a stepping stone to gain a better understanding before moving onto writing a doubly-linked queue class for an assignment.

Here's the code:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedList<T> implements Iterable<T> {
    private Node first;
    private Node last;
    private int N;

    public LinkedList() {
        first = null;
        last = null;
        N = 0;
    }

    public void add(T item) {
        if (item == null) { throw new NullPointerException("The first argument for addLast() is null."); }
        if (!isEmpty()) {
            Node prev = last;
            last = new Node(item, null);
            prev.next = last;
        }
        else {
            last = new Node(item, null);
            first = last;
        }
        N++;
    }

    public boolean remove(T item) {
        if (isEmpty()) { throw new IllegalStateException("Cannot remove() from and empty list."); }
        boolean result = false;
        Node prev = first;
        Node curr = first;
        while (curr.next != null || curr == last) {
            if (curr.data.equals(item)) {
                // remove the last remaining element
                if (N == 1) { first = null; last = null; }
                // remove first element
                else if (curr.equals(first)) { first = first.next; }
                // remove last element
                else if (curr.equals(last)) { last = prev; last.next = null; }
                // remove element
                else { prev.next = curr.next; }
                N--;
                result = true;
                break;
            }
            prev = curr;
            curr = prev.next;
        }
        return result;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private class Node {
        private T data;
        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public Iterator<T> iterator() { return new LinkedListIterator(); }

    private class LinkedListIterator implements Iterator<T> {
        private Node current = first;

        public T next() {
            if (!hasNext()) { throw new NoSuchElementException(); }
            T item = current.data;
            current = current.next;
            return item;
        }

        public boolean hasNext() { return current != null; }

        public void remove() { throw new UnsupportedOperationException(); }
    }

    @Override public String toString() {
        StringBuilder s = new StringBuilder();
        for (T item : this)
            s.append(item + " ");
        return s.toString();
    }

    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        while(!StdIn.isEmpty()) {
            String input = StdIn.readString();
            if (input.equals("print")) { StdOut.println(list.toString()); continue; }
            if (input.charAt(0) == ('+')) { list.add(input.substring(1)); continue; }
            if (input.charAt(0) == ('-')) { list.remove(input.substring(1)); continue; }
            break;
        }
    }
}

Note: It's a pretty basic implementation of a singly-linked-list. The 'T' type is a generic type placeholder. Basically, this linked list should work with any type that inherits from Object. If you use it for primitive types be sure to use the nullable class equivalents (ex 'Integer' for the 'int' type). The 'last' variable isn't really necessary except that it shortens insertions to O(1) time. Removals are slow since they run in O(N) time but it allows you to remove the first occurrence of a value in the list.

If you want you could also look into implementing:

• addFirst() - add a new item to the beginning of the LinkedList
• removeFirst() - remove the first item from the LinkedList
• removeLast() - remove the last item from the LinkedList
• addAll() - add a list/array of items to the LinkedList
• removeAll() - remove a list/array of items from the LinkedList
• contains() - check to see if the LinkedList contains an item
• contains() - clear all items in the LinkedList

Honestly, it only takes a few lines of code to make this a doubly-linked list. The main difference between this and a doubly-linked-list is that the Node instances of a doubly-linked list require an additional reference that points to the previous element in the list.

The benefit of this over a recursive implementation is that it's faster and you don't have to worry about flooding the stack when you traverse large lists.

There are 3 commands to test this in the debugger/console:

• Prefixing a value by a '+' will add it to the list.
• Prefixing with a '-' will remove the first occurrence from the list.
• Typing 'print' will print out the list with the values separated by spaces.

If you have never seen the internals of how one of these works I suggest you step through the following in the debugger:

• add() - tacks a new node onto the end or initializes the first/last values if the list is empty
• remove() - walks the list from the start-to-end. If it finds a match it removes that item and connects the broken links between the previous and next links in the chain. Special exceptions are added when there is no previous or next link.
• toString() - uses the foreach iterator to simply walk the list chain from beginning-to-end.

While there are better and more efficient approaches for lists like array-lists, understanding how the application traverses via references/pointers is integral to understanding how many higher-level data structures work.

Answer 4

Hint 1: read the description of linked lists at http://en.wikipedia.org/wiki/Linked_list

Hint 2: the Java implementation of LinkedList is a doubly linked list. Yours is a singly linked list. The algorithms don't directly apply.

---

Also:

... but creating [a linked list class] from scratch makes no sense whatsoever.

It depends on what the required outcome of the work is. If the goal is to produce code that meets certain functional / non-functional requirements, then you are right. If the real goal is for you to learn how to program / design APIs / implement non-trivial data structures, then the utility of the final product is almost entirely irrelevant.

And thus magically we have a linked list

What you actually have there is a open data type, that could be used to build a (sort of) list. But that is not what your teacher wants. And it certainly would not be considered to be a useful list abstraction. A useful abstraction would include:

• methods to do the things that programmers don't want to have to repeat over and over again, and

• an abstraction layer that stops programmers "breaking" the list; e.g. by accidentally creating a cycle, or accidentally stitching a sublist in two lists to create an inverted tree.

Answer 5

Sure, a Linked List is a bit confusing for programming n00bs, pretty much the temptation is to look at it as Russian Dolls, because that's what it seems like, a LinkedList Object in a LinkedList Object. But that's a touch difficult to visualize, instead look at it like a computer.

LinkedList = Data + Next Member

Where it's the last member of the list if next is NULL

So a 5 member LinkedList would be:

LinkedList(Data1, LinkedList(Data2, LinkedList(Data3, LinkedList(Data4, LinkedList(Data5, NULL)))))

But you can think of it as simply:

Data1 -> Data2 -> Data3 -> Data4 -> Data5 -> NULL

So, how do we find the end of this? Well, we know that the NULL is the end so:

public void append(LinkedList myNextNode) {
  LinkedList current = this; //Make a variable to store a pointer to this LinkedList
  while (current.next != NULL) { //While we're not at the last node of the LinkedList
    current = current.next; //Go further down the rabbit hole.
  }
  current.next = myNextNode; //Now we're at the end, so simply replace the NULL with another Linked List!
  return; //and we're done!
}

This is very simple code of course, and it will infinitely loop if you feed it a circularly linked list! But that's the basics.

Answer 6

Linked list to demonstrate Insert Front, Delete Front, Insert Rear and Delete Rear operations in Java:

import java.io.DataInputStream;
import java.io.IOException;


public class LinkedListTest {

public static void main(String[] args) {
    // TODO Auto-generated method stub      
    Node root = null;

    DataInputStream reader = new DataInputStream(System.in);        
    int op = 0;
    while(op != 6){

        try {
            System.out.println("Enter Option:\n1:Insert Front 2:Delete Front 3:Insert Rear 4:Delete Rear 5:Display List 6:Exit");
            //op = reader.nextInt();
            op = Integer.parseInt(reader.readLine());
            switch (op) {
            case 1:
                System.out.println("Enter Value: ");
                int val = Integer.parseInt(reader.readLine());
                root = insertNodeFront(val,root);
                display(root);
                break;
            case 2:
                root=removeNodeFront(root);
                display(root);
                break;
            case 3:
                System.out.println("Enter Value: ");
                val = Integer.parseInt(reader.readLine());
                root = insertNodeRear(val,root);
                display(root);
                break;
            case 4:
                root=removeNodeRear(root);
                display(root);
                break;
            case 5:
                display(root);
                break;
            default:
                System.out.println("Invalid Option");
                break;
            }
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
    System.out.println("Exited!!!");
    try {
        reader.close();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }       
}

static Node insertNodeFront(int value, Node root){  
    Node temp = new Node(value);
    if(root==null){
        return temp; // as root or first
    }
    else
    {
        temp.next = root;
        return temp;
    }               
}

static Node removeNodeFront(Node root){
    if(root==null){
        System.out.println("List is Empty");
        return null;
    }
    if(root.next==null){
        return null; // remove root itself
    }
    else
    {
        root=root.next;// make next node as root
        return root;
    }               
}

static Node insertNodeRear(int value, Node root){   
    Node temp = new Node(value);
    Node cur = root;
    if(root==null){
        return temp; // as root or first
    }
    else
    {
        while(cur.next!=null)
        {
            cur = cur.next;
        }
        cur.next = temp;
        return root;
    }               
}

static Node removeNodeRear(Node root){
    if(root==null){
        System.out.println("List is Empty");
        return null;
    }
    Node cur = root;
    Node prev = null;
    if(root.next==null){
        return null; // remove root itself
    }
    else
    {
        while(cur.next!=null)
        {
            prev = cur;
            cur = cur.next;
        }
        prev.next=null;// remove last node
        return root;
    }               
}

static void display(Node root){
    System.out.println("Current List:");
    if(root==null){
        System.out.println("List is Empty");
        return;
    }
    while (root!=null){
        System.out.print(root.val+"->");
        root=root.next;
    }
    System.out.println();
}

static class Node{
    int val;
    Node next;
    public Node(int value) {
        // TODO Auto-generated constructor stub
        val = value;
        next = null;
    }
}
}

Answer 7

Linked List Program with following functionalities

1 Insert At Start
2 Insert At End
3 Insert At any Position
4 Delete At any Position
5 Display 
6 Get Size
7 Empty Status
8 Replace data at given postion
9 Search Element by position
10 Delete a Node by Given Data
11 Search Element Iteratively
12 Search Element Recursively




 package com.elegant.ds.linkedlist.practice;

import java.util.Scanner;

class Node {

    Node link = null;
    int data = 0;

    public Node() {
        link = null;
        data = 0;
    }

    public Node(int data, Node link) {
        this.data = data;
        this.link = null;
    }

    public Node getLink() {
        return link;
    }

    public void setLink(Node link) {
        this.link = link;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

}

class SinglyLinkedListImpl {

    Node start = null;
    Node end = null;
    int size = 0;

    public SinglyLinkedListImpl() {
        start = null;
        end = null;
        size = 0;
    }

    public void insertAtStart(int data) {
        Node nptr = new Node(data, null);
        if (start == null) {
            start = nptr;
            end = start;
        } else {
            nptr.setLink(start);
            start = nptr;
        }
        size++;
    }

    public void insertAtEnd(int data) {
        Node nptr = new Node(data, null);
        if (start == null) {
            start = nptr;
            end = nptr;
        } else {
            end.setLink(nptr);
            end = nptr;
        }
        size++;
    }

    public void insertAtPosition(int position, int data) {
        Node nptr = new Node(data, null);
        Node ptr = start;
        position = position - 1;
        for (int i = 1; i < size; i++) {
            if (i == position) {
                Node temp = ptr.getLink();
                ptr.setLink(nptr);
                nptr.setLink(temp);
                break;
            }
            ptr = ptr.getLink();
        }
        size++;
    }

    public void repleaceDataAtPosition(int position, int data) {
        if (start == null) {
            System.out.println("Empty!");
            return;
        }

        Node ptr = start;
        for (int i = 1; i < size; i++) {
            if (i == position) {
                ptr.setData(data);
            }
            ptr = ptr.getLink();
        }
    }

    public void deleteAtPosition(int position) {
        if (start == null) {
            System.out.println("Empty!");
            return;
        }

        if (position == size) {
            Node startPtr = start;
            Node endPtr = start;
            while (startPtr != null) {
                endPtr = startPtr;
                startPtr = startPtr.getLink();
            }
            end = endPtr;
            end.setLink(null);
            size--;
            return;
        }

        Node ptr = start;
        position = position - 1;
        for (int i = 1; i < size; i++) {

            if (i == position) {
                Node temp = ptr.getLink();
                temp = temp.getLink();
                ptr.setLink(temp);
                break;
            }
            ptr = ptr.getLink();
        }
        size--;
    }

    public void deleteNodeByGivenData(int data) {
        if (start == null) {
            System.out.println("Empty!");
            return;
        }

        if (start.getData() == data && start.getLink() == null) {
            start = null;
            end = null;
            size--;
            return;
        }

        if (start.getData() == data && start.getLink() != null) {
            start = start.getLink();
            size--;
            return;
        }

        if (end.getData() == data) {
            Node startPtr = start;
            Node endPtr = start;

            startPtr = startPtr.getLink();
            while (startPtr.getLink() != null) {
                endPtr = startPtr;
                startPtr = startPtr.getLink();
            }
            end = endPtr;
            end.setLink(null);
            size--;
            return;
        }

        Node startPtr = start;
        Node prevLink = startPtr;
        startPtr = startPtr.getLink();
        while (startPtr.getData() != data && startPtr.getLink() != null) {
            prevLink = startPtr;
            startPtr = startPtr.getLink();
        }
        if (startPtr.getData() == data) {
            Node temp = prevLink.getLink();
            temp = temp.getLink();
            prevLink.setLink(temp);
            size--;
            return;
        }

        System.out.println(data + " not found!");
    }

    public void disply() {
        if (start == null) {
            System.out.println("Empty!");
            return;
        }

        if (start.getLink() == null) {
            System.out.println(start.getData());
            return;
        }

        Node ptr = start;
        System.out.print(ptr.getData() + "->");
        ptr = start.getLink();
        while (ptr.getLink() != null) {
            System.out.print(ptr.getData() + "->");
            ptr = ptr.getLink();
        }
        System.out.println(ptr.getData() + "\n");
    }

    public void searchElementByPosition(int position) {
        if (position == 1) {
            System.out.println("Element at " + position + " is : " + start.getData());
            return;
        }

        if (position == size) {
            System.out.println("Element at " + position + " is : " + end.getData());
            return;
        }

        Node ptr = start;
        for (int i = 1; i < size; i++) {
            if (i == position) {
                System.out.println("Element at " + position + " is : " + ptr.getData());
                break;
            }
            ptr = ptr.getLink();
        }
    }

    public void searchElementIteratively(int data) {

        if (isEmpty()) {
            System.out.println("Empty!");
            return;
        }

        if (start.getData() == data) {
            System.out.println(data + " found at " + 1 + " position");
            return;
        }

        if (start.getLink() != null && end.getData() == data) {
            System.out.println(data + " found at " + size + " position");
            return;
        }

        Node startPtr = start;
        int position = 0;
        while (startPtr.getLink() != null) {
            ++position;
            if (startPtr.getData() == data) {
                break;
            }
            startPtr = startPtr.getLink();
        }
        if (startPtr.getData() == data) {
            System.out.println(data + " found at " + position);
            return;
        }

        System.out.println(data + " No found!");
    }

    public void searchElementRecursively(Node start, int data, int count) {

        if (isEmpty()) {
            System.out.println("Empty!");
            return;
        }
        if (start.getData() == data) {
            System.out.println(data + " found at " + (++count));
            return;
        }
        if (start.getLink() == null) {
            System.out.println(data + " not found!");
            return;
        }
        searchElementRecursively(start.getLink(), data, ++count);
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return start == null;
    }
}

public class SinglyLinkedList {

    @SuppressWarnings("resource")
    public static void main(String[] args) {
        SinglyLinkedListImpl listImpl = new SinglyLinkedListImpl();
        System.out.println("Singly Linked list : ");
        boolean yes = true;
        do {
            System.out.println("1 Insert At Start :");
            System.out.println("2 Insert At End :");
            System.out.println("3 Insert At any Position :");
            System.out.println("4 Delete At any Position :");
            System.out.println("5 Display :");
            System.out.println("6 Get Size");
            System.out.println("7 Empty Status");
            System.out.println("8 Replace data at given postion");
            System.out.println("9 Search Element by position ");
            System.out.println("10 Delete a Node by Given Data");
            System.out.println("11 Search Element Iteratively");
            System.out.println("12 Search Element Recursively");
            System.out.println("13 Exit :");
            Scanner scanner = new Scanner(System.in);
            int choice = scanner.nextInt();
            switch (choice) {
            case 1:
                listImpl.insertAtStart(scanner.nextInt());
                break;

            case 2:
                listImpl.insertAtEnd(scanner.nextInt());
                break;

            case 3:
                int position = scanner.nextInt();
                if (position <= 1 || position > listImpl.getSize()) {
                    System.out.println("invalid position!");
                } else {
                    listImpl.insertAtPosition(position, scanner.nextInt());
                }
                break;

            case 4:
                int deletePosition = scanner.nextInt();
                if (deletePosition <= 1 || deletePosition > listImpl.getSize()) {
                    System.out.println("invalid position!");
                } else {
                    listImpl.deleteAtPosition(deletePosition);
                }
                break;

            case 5:
                listImpl.disply();
                break;

            case 6:
                System.out.println(listImpl.getSize());
                break;

            case 7:
                System.out.println(listImpl.isEmpty());
                break;

            case 8:
                int replacePosition = scanner.nextInt();
                if (replacePosition < 1 || replacePosition > listImpl.getSize()) {
                    System.out.println("Invalid position!");
                } else {
                    listImpl.repleaceDataAtPosition(replacePosition, scanner.nextInt());
                }
                break;

            case 9:
                int searchPosition = scanner.nextInt();
                if (searchPosition < 1 || searchPosition > listImpl.getSize()) {
                    System.out.println("Invalid position!");
                } else {
                    listImpl.searchElementByPosition(searchPosition);
                }
                break;

            case 10:
                listImpl.deleteNodeByGivenData(scanner.nextInt());
                break;

            case 11:
                listImpl.searchElementIteratively(scanner.nextInt());
                break;

            case 12:
                listImpl.searchElementRecursively(listImpl.start, scanner.nextInt(), 0);
                break;

            default:
                System.out.println("invalid choice");
                break;
            }
        } while (yes);
    }
}

It will help you in linked list.

Answer 8

How have I created a linkedlist like this. How does this work? This is all a linked list is. An item with a link to the next item in the list. As long as you keep a reference to the item at the beginning of the list, you can traverse the whole thing using each subsequent reference to the next value.

To append, all you need to do is find the end of the list, and make the next item the value you want appended, so if this has non-null next, you would have to call append on the next item until you find the end of the list.

this.next.Append(word);