LinkedList, have some questions

JavaScript
1

found good totorial on youtube similar to article “how to implement a LinkedList in javascript” which is on freecodecamp site, but they have some differences so I wanted to ask if someone can me help
on freecodecamo site it go like this:

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2

let list = new LinkedList(node1)
console.log(list) prints: 
head: Linstnode { data: 2, next: ListNode { data: 5, next: null } }

this is version from freecodecamp site, there is explained how to getLas, getFirst, getSize and clear method but not insertFirst, insertLast and insertAt…
Question is is there another way of inserting new value/element to list other than explained in tutorial? In tutorial is explained inseringFirst throught function, like this:

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

insertFirst(data){
this.head = new ListNode(data, this.head);
}
let list = new LinkedList()
console.log(list); displays: LinkedList { head: ListNode { data: 100, next: null} }

in second example I deleted

let node1 = new ListNode(2);
let node2 = new ListNode(5);
node1.next = node2;

but is there way with next method to make more then one next like that we could make
let node 1
let node 2
let node 3
let node 4
and with next method make them in order one to another,
Question is… is second example only way of inserting fiirst or last items
and in insertFirst function is its parametar (data) reffered to class’s ListNode data parameter and its this.head reffered to class’s LinkedList constructor this.head?
thank You

2

So I’m having my first coffee of the morning, I see your post, and my brain starts to churn. Thanks for the mind stretch!

So here you’re thinking about LinkedList and ListNode elements, and you’re wondering how to handle inserting as well as getting elements in the list in some sort of order.

But what about removing the abstraction, and creating a “mental model” of your structural pattern? Let’s see what I mean.

Suppose you are a teacher of third grade students, say seventeen of them, and you’re going to take them on a field trip. They’re excited about the trip - going to the Boston Aquarium! :tada:

Now, before we go, we need to arrange a buddy system. Let’s say, as we’re in charge, that we are in the back of the kid parade. Doing this, we can oversee everyone. We will hold the strap of the backpack of the kid in front of us, Janice, keeping track of her. That is our focus, though we as the teacher are keeping track of all the little… Dears.

Janice is told to hold tight to the strap of Benji, who is holding the strap of his best friend Sammy. Each child, in turn, is holding the strap of the backpack in front of them. They don’t have to worry about all the rest or even the kid holding onto them, they only need know about the one who’s wearing the backpack they’re gripping.

See how this is a LinkedList? We track the first student, Janice, who is linked to the Benji. Benji is linked to Sammy, and so on. So we have a concrete model of our data structure.

Now, suppose Ralphie was late with his permission slip, but he’s in. We need to add him to the parade. We have a few options:

  • We can simply tell the last kid in line to hold Ralphie’s strap, adding him to the end of the list (insertLast);
  • We can switch from holding Janice’s strap to holding Ralphie’s, and tell him to hold Janice’s (insertFirst);
  • We can place Ralphie after his friend Sammy - but how do we arrange that? What are those steps? (insertAfter)

These things work, and having a concrete model lets us manipulate the data and see how it works. Let’s try a few more!

What if Janice couldn’t make it after all (removeFirst)? What if Sammy cancelled (remove)? What might be the logic for each situation, in real world application?

Before thinking code, can you see the process?

3

I had to google churn
and

din’t know kid parade exist

When You describe like that it is easy to comprehend, also…in video tutorial there is beneath video small graphic with nodes-spaceholders for two smaller placeholders and more nodes like that, every node is reffered to

class Node{
constructor(data) {
this.data = data;
this.next = null;
}

constructor’s properties this.head and this.next…
and when we make an instance of that class Node… first node in the graphic is no longer empty
first box goes for data and second for next which is null, that part understand
but
who is holding who for a belt here?

let list = new LinkedList(node1)

here variable named list is made, and with keywor new, we create new instance from LinkedList class, but what is with node1 in parenthesses?What it reffers to?

1 Like
4

In the constructor, we see that the thing passed into let list = new LinkedList(...), regardless of what it is, will become the list.head. So, as long as we have manually done const node1 = new ListNode("Janice"), then list.head and node1 are a shared reference.

If we then wanted, we could explicitly tell the first item about it’s neighbor:

list.head.next = new ListNode("Benji");

console.log(list.head.data);
// "Janice"
console.log(list.head.next.data);
// "Benji"

So in my story, the teacher might be the instance of LinkedList, tracking only the head, Janice. Janice, in turn, is only observing her next, Benji.

1 Like
5

My biggest issue with the whole thing is the existence of node1 and node2 in the first place. Having to manually create the ListNode things is, to my mind, silly.

We should be doing something like this:

const buddySystem = new LinkedList("Janice");
buddySystem.append("Benji");
buddySystem.append("Sammy");

// let's see what we got:
console.log(buddySystem.head.data);
// "Janice"
console.log(JSON.stringify(buddySystem.head.next, null, 2) );
// {
//  "head": {
//    "data": "Janice",
//    "next": {
//      "data": "Benji",
//      "next": {
//        "data": "Sammmy",
//        "next": null
//      }
//    }
//  }
//}

// let's add another, only at the *front* of the list!
buddyList.prepend("Alphonse");
buddyList.after("Benji", "Cosette");
// what do we have after Benji now?
console.log( buddyList.find("Benji") );
//ListNode {
//  data: 'Benji',
//  next: ListNode {
//    data: 'Cosette',
//    next: ListNode {
//      data: 'Sammmy', 
//      next: null
//    }
//  }
//}

So when we add something to a LinkedList, we don’t explicitly say “Hey, here’s this NodeList thing, go ahead and add it.” Instead, we say “Hey, list of mine, here’s some data. Either append it, prepend it, or add it after <data>.” We don’t care outside of the LinkedList how it does so - we just want it to track the data for us.

Played around a little and LinkedListsInJavascript - Replit

1 Like
6

Append is better than next method, thank You for explaneing to me in such way, I understand theory you described and concept but I have to do samo pratice more, it is cool, I was thinking that data structures can’t help to understand algorithms but now I see that there is lot of work just with LikedList and actually it makes you think so you pratice problem solving, Thanks again, cheers

1 Like
7

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.