CODEWITHSUNDEEP
javalinked-list
yre
yre

Reputation: 285

What is the head Node of a linked lists? Is it the first Node or a reference to it?

Having trouble understanding linked lists. This is in java. I am writing some methods, add, remove, find. But wondering here, is Head, which is defined as a type Node the actual first Node? does it contain data and a next Node reference? Or does it somehow tell what the data is of the first?

Thanks

Upvotes: 1

Views: 4742

Answers (2)

Stephen P
Stephen P

Reputation: 14830

Generally, not limited to Java, all list nodes are the same, and the "head" node is the first one on the list. This, "head", is usually a variable that is a reference (or a pointer) to the first list node.

A simple singly-linked-list node may look like

class ListNode
{
    Object data;      // The data added to the list
    ListNode next;    // Reference to the next item in the list
}

Then "head" would just be

ListNode head;

that is, a variable named "head" that holds (a reference to) a ListNode. The issue gets somewhat confused in Java because everything (except primitives like int) is a reference — so this looks like "head is a ListNode" when it's actually "head is a reference to a list node".

Pictorially, this is like the following, where I've put the "data" in parens and show "next" pointing to something.

head -> ListNode("foo")next -> ListNode("bar")next -> ListNode("baz")next -> null

The end of the list is found when next holds the null value. You would have to also have a ListNode tail; which would be updated to point to the last thing added to the list.

Here's an extremely simple (and untested) example of the concepts. Java's own java.util.LinkedList is much more complicated, and is parameterized with generics.

class List
{
    ListNode head = null;
    ListNode tail = null;

    public add(Object o)
    {
        ListNode node = new ListNode(o);
        if (head == null) head = node;         // if there's no head yet this is the head
        if (tail != null) tail.next = node;    // if there's a tail point tail at this new node
        tail = node;                           // and this is the new tail
    }
    // need remove() etc other methods
}

Upvotes: 0

Matt
Matt

Reputation: 3760

The head node is the first node in the list. The tail node is the last node in the list.

There's nothing special about either of them.

In your LinkedList class you might have references to head and tail, but the nodes themselves are just nodes.

Upvotes: 1

Related Questions