Reputation: 285
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
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
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