Search code examples
javadata-structureslinked-list

What is the 'head' of a linked list?


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


Solution

  • 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.