4

I'm having a bit of an issue with implementing my circularly linked list. I'm working on a problem that requires you to implement any ADT yourself. I seem to be okay with adding nodes to the list, however I'm in unfamiliar territory when it comes to removing. I included the first two remove methods to give you an idea of where my head is at, how would I go about removing the last node in the list?

public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;
    LinkedList() {
        head = null;
        current = null;
        previous = null;
        tail = null;
        size = 0;
    }

    //checks if list is empty
    public boolean isEmpty() {
        return head == null;
    }
    //add new node to front of circularly linked list
    public void addToFront(E x) {
        if (head == null) {
            head = new Node(x);
        } else {
            Node n = new Node(x);
            x.next() = head;
            head = x;
        }
    }

    public void addtoMiddle(E x) {
        x.next = current.next();
        current.next = x;
        size = size + 1;
    }

    public void addToEnd(E x) {
        x.next = null;
        tail.next() = x;
        tail = x;
        size = size + 1;
    }

    public void removeFirst(E x) {
        if (head = null) {
            System.out.println("Error! List is empty!");
        } else {
            head = current.next();
            size = size + 1;
        }
    }

    public void removeMiddle(E x) {
        previous.next() = current.next();
        current.next() = null;
        size = size + 1;
    }
16
  • Can you provide the Node class as well? Assuming you have links in both directions removing the last node would just require you to go backwards from the head. Shouldn't be too big of a headache. - If you have only links in one direction then loop until you hit a node whose next points to the head. That's your last node then. Commented Sep 30, 2015 at 13:44
  • Can you explain what you mean by 'circularly linked list"? Commented Sep 30, 2015 at 13:44
  • This isn't a circular linked list, just a doubly linked list - which could be made into a circular linked list. A circular linked list never has null in any of the nodes' next and previous fields. Commented Sep 30, 2015 at 13:46
  • @Thomas -- I am a beginner & trying to absorb like a sponge. I know there are mistakes/missing statements & am just looking a push in the right direction. Thank you. What "node class" are you referring to? Commented Sep 30, 2015 at 13:47
  • @pablokunta128 I'll add an answer for formatting reasons. Commented Sep 30, 2015 at 13:48

2 Answers 2

3

In a circular linked list the last node's next points to the head, so you loop through your nodes until node.next.equals( head ). Note that next must never be null and if you have only one node then you have head.next = head.

In a circular doubly linked list you also have a previous node, i.e. you can iterate backwards. In that case your last node is just head.previous.

A small ascii picture:

head -next---> node -next---> node -next---> last
 | ^  <---prev-      <---prev-      <---prev- | ^
 | |                                          | |
 | |_____________________________________next_| |
 |_prev_________________________________________|      
Sign up to request clarification or add additional context in comments.

4 Comments

So in theory all I would need is a "head", "tail", and i'll be able to ascertain the methods for removing/adding the middle/end while using .next & .previous?
A very good way of implementing a circular doubly linked list is to make List extends Node so that the list object has the same pointers as a node. This way, there's no need to distinguish the empty list from a list with nodes.
@laune is there a way we can continue this into chat? I don't have enough reputation yet to initialize the convo however. I'm curious to pick your brain & learn a little more. Thank you
@pablokunta128 you'd probably just need the head but keeping track of the tail would come in handy in certain situations. Just as a side note: addtoMiddle etc. seems a bit odd because you'd basically just add at any location (adding to front and back are just special cases for that) so the term "middle" might be misleading.
0

I know this is not directly an answer to your question but I feel like Thomas has given the needed explanation here.

Since you have a lot of syntax or incompleteness errors in the example I would recommend to comment out all functions so it has no more errors. Then comment them in again one by one correcting every error.

Some advices:

You use class members which are not defined e.g. current, previous.

Decide if next should be a member or function.

You need to define a class for Node (containing its members and functions), like you did for LinkedList.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.