What is the 'head' of a linked list?

Question

I'm working in linked lists in Java, so I'm trying to grasp the concept of a single linked list.

head -> 12 -> 34 -> 56 -> null

head.next would be 12 (also the same as node1). However, what is head then?

Update: What is the difference between a reference and a pointer?

Update2: So if head is 12 and head.next is 34, then doesn't mean this following function skips the first node to see if it's null?

public void add(Object data, int index)
    // post: inserts the specified element at the specified position in this list.
    {
        Node temp = new Node(data);
        Node current = head;
        // crawl to the requested index or the last element in the list,
        // whichever comes first
        for(int i = 1; i < index && current.getNext() != null; i++)
        {
            current = current.getNext();
        }
        // set the new node's next-node reference to this node's next-node reference
        temp.setNext(current.getNext());
        // now set this node's next-node reference to the new node
        current.setNext(temp);
        listCount++;// increment the number of elements variable
    }

Source: http://www.mycstutorials.com/articles/data_structures/linkedlists

Answer 1

What I understood is simple difference. With head pointer list creation is managed by the LinkedList class itself, however without head pointer - the client code requires to keep track of first, and then adding the rest of the nodes

However, both with or without head pointer - creates functional LinkedList

Modern go-to style linkedlist without Head pointer(From Leetcode)

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

To create LinkedList

ListNode listNode = new ListNode(4, new ListNode());
listNode.next = new ListNode(1, new ListNode());
listNode.next.next = new ListNode(10);

Now with head pointer:

public class SingleList {
    Node head;

    static class Node{
        int data;
        Node next;
        Node(int d){data = d;}
    }

    public void insertNode(int n){
        Node new_node = new Node(n);
        if(head == null){
            head = new_node;
        } else{
            Node cur_node = head;
            while(cur_node.next !=null){
                cur_node = cur_node.next;
            }
            cur_node.next = new_node;
        }
    }
}

To create Linkedlist

SingleList singleList1 = new SingleList(6);
singleList1.insertNode(3);

See - linkedlist creation in client program - for above different Linkedlist implementation.

Answer 2

The term “head” has two completely unrelated meanings. The most common (that comes out of Lisp, I believe) is “ the first element of the list.” Judging from your diagram, that is not the meaning you have in mind.

The second meaning refers to a technique to deal with the following issue: If you represent a linked list as just the nodes with data, then when the list is empty, all references (and/or pointers, depending on the language) to the list have to be null, because there is nothing to point at. This creates lots of bookkeeping problems for code that uses the list. A list head solves this problem. It is a list node that contains no actual data. A reference or pointer to the list is always a pointer to the head node. The first element of the list is always head.next. Usually, the existence of the head is hidden in the class that implements a “ linked list with a head.”

Depending on the operations being supported, there can be a similar bookkeeping problem at the end of the list, particularly for doubly linked lists. A list tail node simplifies bookkeeping.

These are also called “ sentinel nodes” in the literature (including the Wikipedia article on linked lists).

Answer 3

Before Anything else It should be noted that head is not a separate node, but just a reference to the first node. It keeps the whole list by storing a pointer to the first node.

Another noted difference is that head is an ordinary local pointer variable which is stored in stack, whereas list nodes gets stored in heap. So In most jargon terms Head is just a local pointer which keeps reference to the first element of a linked list and is mostly initialised with NULL in order to distinguish an empty linked list.

Answer 4

The head of the list refers to the first node of the list. It would make a good name for the variable storing the reference of that node, and I would expect it to contain the null-reference if the list was empty

someLinkedList.head
         |
         |
         v
        ______        ______        ______            
       |    |n|      |    |n|      |    |n|           
       |    |e|      |    |e|      |    |e|           
       | 12 |x| -->  | 34 |x| -->  | 56 |x| --> null
       |    |t|      |    |t|      |    |t|           
       |____|_|      |____|_|      |____|_|           

Depending on context, the tail can refer to different things. The terminology I'm used to says that the tail corresponds to 34 -> 56 -> null in this example, that is, the list that follows the head.

In other contexts, it may be a reference to the last node. In such interpretation, the tail would refer to the 56 node in your example.

---

Regarding your first edit, which happens to be a completely different question:

A pointer is a value corresponding to a memory address. A reference is value referring to some object (or null). You can't do pointer arithmetic on Java references, but otherwise I'd say they are fairly similar.

What may confuse you, is that variables in Java can never contain objects. Objects always live on the heap, and variables contain primitive data types, or references to objects on the heap.

---

Regarding your second edit:

In the example you provided, it looks like the add method skips the first element, and in a sense it does. This is because the implementation has a "dummy"-element as the head. Look at the initialization of the head-variable in the constructor:

head = new Node(null);

I can't understand why they've decided to do that. To me it looks plain stupid.

Answer 5

yes it is just a pointer to the first node