CodeGym/Help with Java Tasks/I don't know how to start it.

Level 50

Kraków

20.11.2022
427views
14comments

I don't know how to start it.

Question about the task

StringLinkedList

Java Syntax, Level 14, Lesson 5

Under discussion

I sat on this task and I had null in my mind. Help me how I start it :(

/*
StringLinkedList
*/

public class Solution {

    public static void main(String[] args) {
        StringLinkedList stringLinkedList = new StringLinkedList();
        stringLinkedList.add("1");
        stringLinkedList.add("2");
        stringLinkedList.add("3");
        stringLinkedList.add("4");
        stringLinkedList.add("5");
        stringLinkedList.add("6");
        stringLinkedList.add("7");
        stringLinkedList.add("8");
        stringLinkedList.add("9");
        stringLinkedList.printAll();
    }
}









public class StringLinkedList {
    private Node first = new Node();
    private Node last = new Node();

    public void printAll() {
        Node currentElement = first.next;
        while ((currentElement) != null) {
            System.out.println(currentElement.value);
            currentElement = currentElement.next;
        }
    }

    public void add(String value) {
        Node third = new Node();
        third.value = value;
        first.value = value;

    }

    public static class Node {
        private Node prev;
        private String value;
        private Node next;
    }
}

Comments (14)

Popular
New
Old

You must be signed in to leave a comment

Vadim “迪姆哥”

Level 35 , Kazakhstan

22 November 2022, 12:41

Hi there, there is nothing wrong with finding a ready-made solution on the Internet, even if the solution is made in another C-style programming language. Then you need to understand how that code works, after that you could implement the same thing in your project.

matemate123

Level 50 , Kraków, Poland

21 November 2022, 08:57

It's time to get acquainted with doubly linked lists. By solving this task, you will understand how a doubly linked list works and you'll be able to add elements to it. You have a StringLinkedList class, which has first and last fields that point to the first and last elements respectively. You need to implement the logic of the add method, which will add elements to the list. Hints: To achieve the correct implementation, it is important to understand that you can iterate over the list both from the first element to the last, and vice versa. So when you add new elements, don't forget to change the references in the adjacent elements. The add method must create a new Node object, which will store the passed value. Before adding a new node, you need to change the last node's reference so that it points to the newly created one, and the newly created node will become the last node. If there is a single element in the list, then the first.next and last.prev fields both point to it. The printAll method was created for debugging. It is not involving in verifying the task. Important: Node first should not store a value. It only points to the first element (first.next); Node last also does not store a value. It only points to the last element (last.prev). Requirements: • When a new element is added, existing elements should get a reference it. • When a new element is added, it should store a reference to the previous element. • The StringLinkedList class's first field should always refer to the first element and not contain the value of the previous element (prev field) or a reference to it. • The StringLinkedList class's last field should always refer to the last element and not contain the value of the next element (next field) or a reference to it.

Thomas

Level 41 , Bayreuth, Germany

21 November 2022, 10:00

useful

I hope you know how a (normal) linked list works (in theory). That is important to not get confused by a doubly linked list. Usually a linked list is a chain of elements called nodes. Each node contains the data and a link to the next Node. You must get used to that. The next link is just a node again, this can link to another node and so on. This looks weird but it is the key of understanding it. now how that'll look in code (usually you'd made that generic but here CG is nice and just requires Strings).

static class Node {
    // the link to the next node
    Node next;
    // here we save the data
    String data;

    // and a constructor that sets the data
    public Node(String data) {
        this.data = data;
    }
}

Nothing complicated here... Just an attribute for the data and an attribute that can save another Node To get this running we put that class in another class that we call StringLinkedList. This class represents the chain while the node is a chain link. The chain class needs to know the first chain link and it gets all the logic (adding new chain links, looping over the chain links, removing etc.). That first chain link (a Node of course) is the only attribute the chain (the linked list) needs to have (at the moment). We call it head.

private Node head;

By default the head is null and when that is the case, the linked list is empty. If we set it to some Node, we have data in the list. Now we need an add method. And before I show you what we have so far in code

public class StringLinkedList {
    static class Node {
        Node next;
        String data;

        public Node(String data) {
            this.data = data;
        }
    }

    private Node head;

    public void add(String data) {

    }
}

Thomas

Level 41 , Bayreuth, Germany

21 November 2022, 10:22

useful

The add method takes the data and saves it in a new node

public void add(String data) {
    Node newNode = new Node(data);
}

Now we need to take care of the link management. It is different for two cases. The linked list is empty or it already has some data. a) if it is empty, then the head, the first element in the chain is our newly created Node. And after that one there is now other element. Means we do not need to do anything else. No next element, no next link to set.

public void add(String data) {
    Node newNode = new Node(data);

    if (head == null) {
        head = newNode;
    }
}

b) If you already have data in the linked list, then you first need to find the tail, the last element in the list. That last element you let point then to your newly created node (btw. there are possibilities to avoid looping over the entire list to find the end - even without an attribute in the main class - you make it a circular linked list and save eg. as the heads prev link a link to the tail or vice versa, you use a tail link in the main class and link its next link to head, but ignore that right now).

public void add(String data) {
    Node newNode = new Node(data);

    if (head == null) {
        head = newNode;
    } else {
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }
}

Now this already should work. You could write a method that outputs your data to verify all is OK.

Thomas

Level 41 , Bayreuth, Germany

21 November 2022, 10:23

useful

@Override
public String toString() {
    StringBuilder sb = new StringBuilder("{");
    Node current = head;
    while (current != null) {
        sb.append(current.data).append(", ");
        current = current.next;
    }
    if (sb.length() > 1) {
        sb.setLength(sb.length() - 2);
    }
    sb.append("}");
    return sb.toString();
}

public static void main(String[] args) {
    StringLinkedList sll = new StringLinkedList();
    sll.add("1");
    sll.add("2");
    sll.add("3");
    sll.add("4");
    sll.add("5");
    sll.add("6");
    System.out.println(sll);
}

Thomas

Level 41 , Bayreuth, Germany

21 November 2022, 10:27

useful

Go through this and play with it till you understand what's happening. If you now want to implement a doubly linked list, then this is easier and somewhat more difficult at the same time. The difference is, that you can go through the linked list only in one direction. You only have next links in the nodes and hence you just need a head attribute (start link) in the linked list class. In the doubly linked list you can move in both directions. Means you need a prev link in the node class and cause you now have prev and next links you should add start and end attributes to the doubly linked list class (usually named head and tail), too. The add method now needs to handle some more stuff. Easiest is to add (of course to the tail). The old tail's next link needs to be set, the new elements prev link needs to be set and finally you set the new tail. That's it ;) (Oh, the easier part is, that you do not need to iterate to the tail cause you already have a link to it in the main class). Good luck. And no worries. This is really a very hard task. (Oh, and I do not know if the code you posted above is partially given by CG and if so what parts. Of course you could code a the head and tail elements as nodes with a null value but for me that seems more effort and not that straight forward. That's why I have chosen the usual approach).

matemate123

Level 50 , Kraków, Poland

21 November 2022, 14:53

I'm appreciate your time Thomas, and your very generous reply for my problem. I sit down and analize what you wrote to me, It's big motivation to not waste your time. Thanks a lot!

matemate123

Level 50 , Kraków, Poland

21 November 2022, 16:03

It's original code (only I wrote this shit in add method). Originally is empty

public void add(String value) {
}

matemate123

Level 50 , Kraków, Poland

22 November 2022, 11:12

I'm done, maybe I'm too stupid now for this, but my mind can't operate on that.

Thomas

Level 41 , Bayreuth, Germany

22 November 2022, 11:40

useful

As said, that's a hard task. Let's add the doubly linked list class necessities now. From my post above: In the doubly linked list you can move in both directions. Means you need a prev link in the node class and cause you now have prev and next links you should add start and end attributes to the doubly linked list class (usually named head and tail), too.

public class StringLinkedList {
    static class Node {
        Node prev;  // new
        Node next;
        String data;

        public Node(String data) {
            this.data = data;
        }
    }

    Node head, tail;  // tail is new

    public void add(String data) {
    }
}

We've added now the prev link to the Node class and the tail to the main class. No surprises Again from my post above The add method now needs to handle some more stuff. Easiest is to add (of course to the tail). The old tail's next link needs to be set, the new elements prev link needs to be set and finally you set the new tail. Look at the code and the comments, I implemented that and marked it as First, Second and Third. The rest should be known from the normal linked list

Thomas

Level 41 , Bayreuth, Germany

22 November 2022, 11:41

useful

public void add(String data) {
    // first create a new node using the passed data
    Node newNode = new Node(data);

    // a) no data in the list, then the lists start and end (head and tail are now that newly created node)
    // and cause there are no prev and next nodes, we leave the nodes prev and next links as null, that serves as
    // start and end marker
    if (head == null) {
        head = tail = newNode;  // above is the same as before, here the changes start, setting also the tail
    } else {
        // b) there already is data in the doubly linked list, means head and tail are pointing to a Node
        // We add that newly created node to the end of the list, the tail. For that three things we need to set,
        // the old tails next link, the new tails prev link and finally the new tail
        // - First: right now the tail's next link is pointing to null, we make it point to the newNode
        tail.next = newNode;
        // - Second: the new tails (the newNode) prevLink (that's the old tail)
        newNode.prev = tail;
        // - Third: the lists tail attribute has changed. It is now the newNode
        tail = newNode;
    }
}

As said, creating the new node and the a) condition is straight forward and like before in the single linked list. The somewhat confusing part is to change the prev link for the new node and the next link for the old tail node and then to set the new node as the tail. Now just add test methods and you can start using it. You also could add a size attribute and increment it when adding new elements. Then write a size() and isEmpty() method... ;) You probably will need to press that code somehow into CGs requirements. But that shouldn't be such a big problem anymore. In the end you could have something like that.

Thomas

Level 41 , Bayreuth, Germany

22 November 2022, 11:46

useful

public class StringLinkedList {
    static class Node {
        Node prev;
        Node next;
        String data;

        public Node(String data) {
            this.data = data;
        }
    }

    Node head, tail;

    public void add(String data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    public void printForward() {
        Node current = head;
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    public void printBackward() {
        Node current = tail;
        while (current != null) {
            System.out.println(current.data);
            current = current.prev;
        }
    }

    public static void main(String[] args) {
        StringLinkedList list = new StringLinkedList();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");
        list.add("6");
        list.printForward();
        list.printBackward();
    }
}

matemate123

Level 50 , Kraków, Poland

28 November 2022, 17:13

I'm little closer validate task, but I need more time. It's harder task for me, I did every tasks from 1 to 14 lvl (without this and second LinkedList task). But that is something my mind have troubles. I understand LinkedList idea, but I can't transfer that on my code. I went ahead with course, but sometimes (once a day) I go back and try resolve this. I very appreciate your help Thomas, one day I'll success, I'm very grateful for your time :)

Thomas

Level 41 , Bayreuth, Germany

20 November 2022, 22:16

Don't know the task. You should attach the description...