Singly Linked List Implementation

Jyr

Alright, I'm trying to implement a (Singly) Linked List via my textbook (Goodrich & Tamassia, Algorithm Design, 2001), and so far so good.

Now, the problem I'm running into, is that I cannot test it properly For example, if I would insert a node via my insertFirst method, how would I still be able to retrieve it to be able to use it for a method like swapElements?

I thought about working via elements, but then I'll run into problems when I have nodes with the same element. So, how should this work in general? I'm sorry if my question is relatively easy or vague, in that case please let me know how I can improve it as I'm fairly new to data structures.

Here's my code;

public class Node<E> implements Position<E> {

    private Node<E> next;
    private E element;

    public Node(Node<E> next, E element) {
        this.next = next;
        this.element = element;
    }

    public Node(E element) {
        this.element = element;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }

    public Node<E> getNext() {
        return next;
    }

    public void setElement(E element) {
        this.element = element;
    }

    public E element() {
        return element;
    }

    public String toString() {
        return ("Element: " + element);
    }

}

and

public class SinglyLinkedListImp<E> implements List<E> {

    private Node<E> head;
    private int size;

    public SinglyLinkedListImp() {
        this.head = null;
        this.size = 0;
    }

    public Node<E> first() {
        return head;
    }

    public Node<E> last() {
        Node<E> current = head;
        while (current.getNext() != null) {
            current = current.getNext();
        }
        return current;
    }

    public boolean isFirst(Node<E> n) {
        return (head == n);
    }

    public boolean isLast(Node<E> n) {
        return (n.getNext() == null);
    }

    public Node<E> before(Node<E> n) {
        Node<E> current = head;
        while (current.getNext() != n) {
            current = current.getNext();
        }
        return current;
    }

    public Node<E> after(Node<E> n) {
        return n.getNext();
    }

    public Node<E> replaceElements(Node<E> n, E element) {
        Node<E> current = head;
        Node<E> previous = null;
        while (current != n) {
            previous = current;
            current = current.getNext();
        }
        Node<E> newLink = new Node<E>(current.getNext(), element);
        previous.setNext(newLink);
        return current;
    }

    public void swapElements(Node<E> n, Node<E> k) {
        E tmp = n.element();
        n.setElement(k.element());
        k.setElement(tmp);
    }

    public void insertFirst(E element) {
        head = new Node<E>(head, element);
        size++;
    }

    public void insertLast(E element) {
        if (head == null) {
            head = new Node<E>(head, element);
        } else {
            Node<E> current = head;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            current.setNext(new Node<E>(null, element));
        }
        size++;
    }

    public void insertBefore(Node<E> n, E element) {
        Node<E> current = head;
        Node<E> previous = null;
        while (current.getNext() != n) {
            previous = current;
            current = current.getNext();
        }
        previous.setNext(n);
    }

    public void insertAfter(Node<E> n, E element) {
        Node<E> current = head;
        while (current != n) {
            current = current.getNext();
        }
        current.setNext(n);
    }

    public void remove(Node<E> n) {
        Node<E> current = head;
        Node<E> previous = null;
        while (current != n) {
            previous = current;
            current = current.getNext();
        }
        previous.setNext(current.getNext());
        size--;
    }

    public int size() {
        return size;
    }

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

    public void display() {
        if (head == null) {
            System.out.println("Empty list.");
        } else {
            Node<E> current = head;
            while (current != null) {
                System.out.println(current.toString());
                current = current.getNext();
            }
        }
    }

}

Note that the SinglyLinkedListImp class is not totally done yet (some methods will give errors if the list is empty). I don't think it's needed to provide the code for the two interfaces, but let me know if so.

Nick L.

In your implementation, you have set some methods (like getNext etc) that can be used in order to iterate the collection. A scenario that I can think of it is having retrieved any element of the list in one operation and then apply the editing on the collection based on the element (like swapElements) afterwards.

What I suggest you do though (and will probably make things clear) is add a retrieval method of an element by index: a method get(int index) would return the element placed on the index given as argument. In fact, the LinkedList collection standard API in Java has such a method. The logic behind this is simple: get the next node till the iteration cycles number reaches the index number.

UPDATE: In order to apply element swapping, obviously the Nodes involved MUST be a part of the list, otherwise there is no meaning in this. As also suggested, swapElements might be basically used for in-class purposes, so unless you have a good reason for it, declare it private.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related