Good evening! Here's our prompt for today.

Let's implement a linked list, a data structure that serves as one of the fundamental building blocks of many other data structures.

A linked list is defined as a lineardata structurewhere each element is a separate object. Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node.

Traditionally we have the following LinkedListNode class definition:

1class LinkedListNode {
2  constructor(val, next = null) {
3    this.val = val;
4    this.next = next;
5  }
6}

We can readily create a entire linked list by writing statements like:

1const list1 = new LinkedListNode(2);
2list1.next =  new LinkedListNode(3);

This will append the node to the end of our new list, and does the job most of the time. However, what if we wanted to make things cleaner and implement a class to help us append and prepend nodes?

Given the following skeleton for a Linked List class, can you fill in the #append and #prepend methods? We will call .head on an instance of your class to get the head node.

1class LinkedList {
2  constructor() {
3    this.head = null;
4    this.tail = null;
5  }
6  
7  prepend(value) {}
8  
9  append(value) {}
10};

Constraints

• The numbers in the node to be added are within the integer limits
• Expected time complexity for appending and prepending : O(1)
• Expected space complexity for appending and prepending : O(1)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

class LinkedListNode:

    def __init__(self, val, next=None):

        self.val = val

        self.next = next

​

​

class LinkedList:

    def __init__(self):

        self.head = None

        self.tail = None

​

    def prepend(self, newVal):

        pass

​

    def append(self, newVal):

        pass

​

​

# Node definition

class Node:

  def __init__(self, val):

    self.val = val

    self.next = None

​

def create_nodes(head, nodes):

  for val in nodes:

    new_node = Node(val)

    head.next = new_node

Here's how we would solve this problem...

How do I use this guide?

To start off, any kind of prepending and appending methods will need to know where the beginning and end of the linked list is. Thus, we know we need a head and tail reference, so we can start with this snippet as the function constructor.

xxxxxxxxxx

class LinkedList {

  constructor() {

    this.head = null;

    this.tail = null;

  }

}

Now, we'd like to append nodes. Appending is the act of adding to the list. In the event that a linked list does not have a tail reference, we would simply set the value of the last node's next attribute to that of the new node.

However, in this case, we'll just set it to the next of tail, which will always be the last node in the chain.

Note that, as usual, before we set the next value, we need to new up/create a new LinkedListNode that actually contains the actual value.

xxxxxxxxxx

append(newVal) {

  const newNode = new LinkedListNode(newVal);

  if (!this.head) {

    this.head = newNode;

    this.tail = newNode;

  } else {

    this.tail.next = newNode;

    this.tail = newNode;

  }

}

On the other hand, we may want to prepend nodes-- that is, add to the start, before the head node.

To prepend nodes, we can create a new node, and set its next to our current head. This will introduce a new entity in the beginning of our links:

xxxxxxxxxx

4 -> 5 -> 6

newNode = 3

3 -> 4 -> 5 -> 6

Translated in code, this would look like the following:

xxxxxxxxxx

prepend(newVal) {

  const currentHead = this.head;

  const newNode = new LinkedListNode(newVal);

  newNode.next = currentHead;

  this.head = newNode;

​

  if (!this.tail) {

    this.tail = newNode;

  }

}

Later on, when we remove nodes at the beginning or end, we'll need to account for the switch in this.head and this.tail.

Complexity for Final Solution

Since we have a reference to both head and tail nodes, the time complexities for both append and prepend are O(1) constant time complexity. Without a tail pointer, for append() we would have to iterate through the entire list in O(n) time where the list is length n. Each linked list node takes up a constant amount of space, for O(1) space complexity.