Singly Linked-Lists

Rewriting IntList

• We may rewrite the IntList data structure to make it easier to use.
• For starters, we may add abstraction by creating an IntNode for each element in the list.

public class IntNode {
    public int item;
    public IntNode next;

    public IntNode(int i, IntNode n) {
        item = i;
        next = n;
    }
}

• With the primary list logic created, we may simply create a “wrapper class” to contain other helper methods to better interact with the list.
  • Moreover, this wrapping allows us to encapsulate certain parameters to prevent undesired behavior. We may set first as a private instance varialbe so that the enduser cannot freely manipulate it to produce undesired behaviors such as a cyclical linked list.
• We may also nest our IntNode class within our SLList class for better organization. In this case, our IntNode class does not need to access members of a specific instance of SLList, so it may be created as a static class too as it is common to all instances of SLList.

public class SLList {
    public static class IntNode {
        public int item;
        public IntNode next;
    
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

    private IntNode first;

    public SLList(int x) {
        first = new IntNode(x, null);
    }

    public void addFirst(int x) {
        first = new IntNode(x, first);
    }

    public int getFirst() {
        return first.item;
    }

    public void addLast(int x) {
        IntNode dummy = first;
        while (dummy.next != null) {
            dummy = dummy.next;
        }
        dummy.next = new IntNode(x, null);
    }

    private static int size(IntNode p) {
        if (p.next == null) {
            return 1;
        }
        return 1 + size(p.next);
    }

    public int size() {
        return size(first);
    }
}

SLList L = new SLList(1);
L.addFirst(2);
L.addLast(3);
L.size();

3

• For the size method, we have a private static method and a public method with the same name.
  • This is allowed because the method signature of the two methods are the exact same.
  • One size takes no arguments, and the other one takes one argument.
  • Methods that have the same name but different signatures are called overloaded.
• The size method has an O(n) complexity though. We may speed up the algorithm by caching a size at the cost of using more memory.

public class SLList {
    public static class IntNode {
        public int item;
        public IntNode next;
    
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

    private IntNode first;
    private int size;

    public SLList(int x) {
        first = new IntNode(x, null);
        size = 1;
    }

    public void addFirst(int x) {
        first = new IntNode(x, first);
        size+=1;
    }

    public int getFirst() {
        return first.item;
    }

    public int get(int i) {
        IntNode dummy = first; 
        while (i > 0 && dummy.next != null) {
            dummy = dummy.next;
            i--;
        }
        return dummy.item;
    }

    public void addLast(int x) {
        IntNode dummy = first;
        while (dummy.next != null) {
            dummy = dummy.next;
        }
        dummy.next = new IntNode(x, null);
        size+=1;
    }

    public int size() {
        return size;
    }
}

SLList L = new SLList(1);
L.addFirst(2);
L.addLast(3);
L.get(1);

1

The Empty List.

• We may also add a constructor that creates an empty list to our SLList class.

public SLList() {
    first = null;
    size = 0;
}

• However, with this empty list, if we tried to add to the end of the list, we’d see that we’d get a NullPointerException as our dummy node would be null, and would not have the next attribute.
  • To fix this, we could create a special case for an empty list:

public void addLast(int x) {
    IntNode dummy = first;
    if (dummy == null) {
        first = new IntNode(x, null);
        return;
    }
    while (dummy.next != null) {
        dummy = dummy.next;
    }
    dummy.next = new IntNode(x, null);
    size+=1;
}

• However, having too many special cases could end up making our code overly complex.
• Instead, let’s use a sentinel node for an empty list. This sentinel node just holds a placeholder value, which allows our list to still have a dummy node to add future nodes to, even when there are no actual nodes.
  • We would have to account for this sentinel node in all methods too, but to the end user, it will feel like the sentinel node was never there.

public class SLList {
    public static class IntNode {
        public int item;
        public IntNode next;
    
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }

    private IntNode sentinel;
    private int size;

    public SLList(int x) {
        sentinel = new IntNode(1337, null);
        sentinel.next = new IntNode(x, null);
        size = 1;
    }

    public SLList() {
        sentinel = new IntNode(1337, null);
        size = 0;
    }

    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size+=1;
    }

    public int getFirst() {
        return sentinel.next.item;
    }

    public int get(int i) {
        IntNode dummy = sentinel; 
        while (i > -1 && dummy.next != null) {
            dummy = dummy.next;
            i--;
        }
        return dummy.item;
    }

    public void addLast(int x) {
        IntNode dummy = sentinel;
        while (dummy.next != null) {
            dummy = dummy.next;
        }
        dummy.next = new IntNode(x, null);
        size+=1;
    }

    public int size() {
        return size;
    }
}

SLList L = new SLList(1);
L.addFirst(2);
L.addLast(3);
L.get(2);

3