Single linked list in java
-
14-11-2019 - |
Question
In the following code, I am trying to understand one thing in the insertFirst()
method that
Why is the last statement first =newLink;
and not first.next=new Link;
Will it be wrong? Isn't there a "next" in first?
I know this code is right and I know that a node needs to be inserted at the beginning and all, but I need help understanding just one statement.
Is first =newLink;
and first.next=new Link;
not the same thing?
public class LinkedList {
private Link first;
public LinkedList()
{
first = null;
}
public boolean isEmtpy()
{
return(first==null);
}
public void insertFirst(int id, int dd)
{
Link newLink=new Link(id,dd);
newLink.next=first;
first =newLink;
}
}
Solution
Why is the last statement
first =newLink;
and notfirst.next=new Link;
Because you're inserting a new first element and the "next" element is the old first element, which was set on the previous line.
Is first =newLink; and first.next=new Link; not the same thing?
No. first
is the first and first.next
is the second.
OTHER TIPS
No, it's right: the list inserts new links at the beginning. The old "first" becomes the new link's "next", and the new link is the new "first".
This is because you want to put new element to the beginning, so you must set new element to the head of list and this element should point on "old-head", and then you have:
new_elemnt->old_head->...
LinkedList::first
is not a guard element. It really points to the first element of the list. If LinkedList::first == null
, then the list is empty. If Link::next == null
, then it's the last element (the null
is called a guard element in this case).
Simple example of SingleLinkedList in Java
package com.ds;
public class SingleLinkedList {
private Node head;
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.insert(5);
linkedList.insert(15);
linkedList.insert(45);
linkedList.insert(55);
linkedList.insert(58);
linkedList.insert(25);
// Print value of Single Linked list.
linkedList.print();
// delete node from tail side.
linkedList.delete();
linkedList.delete();
linkedList.delete();
linkedList.delete();
linkedList.delete();
/*linkedList.delete();
linkedList.delete();
linkedList.delete();
linkedList.delete();*/
linkedList.print();
}
SingleLinkedList() {
head = null;
}
void insert(int val) {
Node temp = new Node();
temp.data = val;
temp.next = null;
if (head == null) {
head = temp;
} else {
Node k = head;
while (k.next != null) {
k = k.next;
}
k.next = temp;
}
}
// delete from tail.
void delete() {
// if it's first node
if (head == null || head.next == null) {
head = null;
} else {
Node n = head;
Node t = head;
while (n.next != null) {
t = n;
n = n.next;
}
t.next = null;
}
}
void print() {
Node k = head;
while (k != null) {
System.out.println(k.data);
k = k.next;
}
}
Node reverse() {
Node h = head;
Node p = null;
Node t = null;
while (h != null) {
t = h.next;
h.next = p;
p = h;
h = t;
}
return p;
}
class Node {
private int data;
private Node next;
}
}