CODEWITHSUNDEEP
c#data-structureslinked-list
Sarvesh Patil
Sarvesh Patil

Reputation: 95

How does a node get added in a linked list and become its new head?

public void Add(Node<T> newItem)
{
    if(this.First==null)
    {
        this.First = newItem;
        this.Last = newItem;
    }
    else
    {
        newItem.next = this.First;
        this.First = newItem;
    }
    Count++;
}

I don't understand how the else block actually works. I understand that newItem.next points to the First node and then subsequently on next line we assign newItem to First. But I find it hard to see how this manipulation works and how the new node is added in case there already existed a node previously.

Upvotes: 2

Views: 262

Answers (3)

trincot
trincot

Reputation: 350667

It might help to visualise this. Let's say we already have a list with two nodes, having values 2 and 3:

 this
  │
  ▼
┌──────────┐
│ First: ──────────────┐
└──────────┘           ▼
                    ┌──────────┐   ┌──────────┐
                    │ data: 2  │   │ data: 3  │
                    │ next: ─────► │ next:null│
                    └──────────┘   └──────────┘

Now newItem is created, having value 1:

 this
  │
  ▼
┌──────────┐
│ First: ──────────────┐
└──────────┘           ▼
     ┌──────────┐   ┌──────────┐   ┌──────────┐
     │ data: 1  │   │ data: 2  │   │ data: 3  │
     │ next:null│   │ next: ─────► │ next:null│
     └──────────┘   └──────────┘   └──────────┘
       ▲
       │
      newItem

Note that at this stage, this newItem is not part of a linked list chain. That is what a call to Add(newItem) will establish. When that method executes, we get in the else block and execute newItem.next = this.First;, which modifies the next property of this newItem object, so it references the same object as this.First references. And so we get this:

 this
  │
  ▼
┌──────────┐
│ First: ──────────────┐
└──────────┘           ▼
     ┌──────────┐   ┌──────────┐   ┌──────────┐
     │ data: 1  │   │ data: 2  │   │ data: 3  │
     │ next: ─────► │ next: ─────► │ next:null│
     └──────────┘   └──────────┘   └──────────┘
       ▲
       │
      newItem

Although the node now refers to a node in the linked list, it is itself still not part of the linked list itself. For that we need the second statement in that else block: this.First = newItem;

The result is:

 this
  │
  ▼
┌──────────┐
│ First: ────┐
└──────────┘ ▼
     ┌──────────┐   ┌──────────┐   ┌──────────┐
     │ data: 1  │   │ data: 2  │   │ data: 3  │
     │ next: ─────► │ next: ─────► │ next:null│
     └──────────┘   └──────────┘   └──────────┘
       ▲
       │
      newItem

And now the goal is achieved. The list now starts with the value 1, then 2, then 3.

Upvotes: 5

Manish
Manish

Reputation: 6286

It would be a bit difficult to explain without some graphics but let me give it a try.

  1. Initially, our linked list is empty. First-> NULL
  2. Then we add a new item by calling Add, say Item1.
  3. Because this.First is null, it will start pointing to this newItem. Remember, First here is nothing but a pointer pointing to the newItem now. So our linked list now is: First -> Item1
  4. Now we add another item but this time the linked list is not empty. Say, Item2
  5. Looking at the code, the intention is to add the new item at the beginning of the linked list. So, we make the next pointer of the newItem point to First making them linked to each other. Our linked list now is: Item2.next -> First
  6. Now because we only want to maintain the First (head) pointer we point it to the current first/ or head node which is nothing but the newly added item. Hence this.First = newItem.

Linked list now is: Item2 -> Item1 with First pointing to Item2.

Upvotes: 1

cemahseri
cemahseri

Reputation: 565

if the list's first item is null, which means the list is empty, it set's first and the last (since it's the only item, it will be first and the last item) item to the newItem.

Or else, it links the first item to the new item as its next node, and sets the first item to the newItem. It simply puts newItem in the beginning of the list, then links former first item to it.

Upvotes: 1

Related Questions