In simple words, a collection which can contain many objects of the same type, like the ArrayList is a LinkedList.
Arraylist
uses dynamic array. Lets say we take an array size of 5. we gave input
as 1,2,3,4,5. Now, if we gave it one more value, It creates a new
arraylist of sizex2 = 5x2 = 10. it copies data from the first arraylist
and then appends the new value.
if
something is removed between the arraylist, every value shifts one by
one. Same is with the insert. From this, we can say that arraylist is
better for storing values instead of manipulating it.
So what is the difference between ArrayList and LinkedList?
In this blog we will take a look into Singular LinkedList and code related to it.
For a quick overview, contents are,
- What is LinkedList?
- Difference between arraylist and linkedlist
- Creating Node class
- Add Node at beginning
- Extend a node
- Delete first node
- Delete last node
What is LinkedList?
LinkedList is nothing but nodes connected to each other.
A node is a point of intersection/connection within a data communication network.A node contents two things: data and address of the next node(data). The starting node is named as head. The last node always points to null address.nodes are saved in heaps and connected by last node which contains its address. Head is already known from the start.
Difference between arraylist and linkedlist
1. LinkedList Insert is easy. You just need to point previous node to the new node and point new node to the next node where you want to insert. Therefore, its complexity is O(1). Arraylists is O(N)
2. To search an element in Linkedlist, it iterates all over the listso its complexity is O(1) and arraylist is O(1).
3. Linked is in non continuous as its not connected to each other, instead its connected by reference value(next value address).
4. Manipulation with LinkedList is faster than ArrayList.
5. The location for the elements of a linked list is not continious. Arraylist is continuous.
6. In LinkedList, an empty list is created when a LinkedList is initialized. When an ArrayList is initialized, a default capacity of 10 is assigned to the ArrayList.
Creating Node class
///creating class named as LinkedLst
class LinkedLst{
class Node{
String data; //initializing data
Node next; //initializing next
Node(String data){
this.data = data; //declaring data
this.next=null; //declaring next as null since last value always points to null
}
}
public static void main(String[] args) {
LinkedLst list = new LinkedLst(); //creating a linkedlist
}
}
We just created a way to save node, but we need to make a new function to add values in it.
Add Node at beginning
what we would to append it is, we would first say that it should point at the actual head. so now, that head will come at second position. Now we just have to tell that our new node is the new head
public void addfront(String data){
Node newnode = new Node(data);//declaring the data given as node
if(head == null){ //corner case: if no value in list, make it the first value
head = newnode;
return;
}
newnode.next = head; //pointinhg our data to the head, so the real head will become 2nd vlue
head = newnode; //making our new data as head // cancelling the pointer of head and making it to point at new node
}
To print the list, just print using while loop till node(taken as head to start from starting) is not null
public void prnt(){
Node currNode = head;
while(currNode != null) {
System.out.print(currNode.data+" -> ");
currNode = currNode.next;
}
System.out.println("null");
return;
}
Extend a node
To extend, we just need to find last node and make it point towards our new node. the new node always points as null.
public void extnd(String data){
Node newnode = new Node(data);//declaring the data given as node
if(head == null){ //corner case: if no value in list, make it the first value
head = newnode;
return;
}
node currnode = head; //for iterating. so that actual head value won't change
while(currnode.next != null){ //whether next value is null
currnode = currnode.next; //iterate
}
currnode.next = newnode; //pointing last node towards new node
}
Delete first node
To delete first, just make 2nd value as head.
public void delfst(){
if(head == null){ //corner case: if no value in list
System.out.println("empty list");
return;
}
head = this.head.next; //making 2nd value as head
}
Delete last node
to delete last node, find second last and point it towards null.
public void dellst(){
if(head == null){ //corner case: if no value in list
System.out.println("empty list");
return;
}
currnode = head; //to iterate. this will search secondlast node
lastnode = head.next; //to get last node
while(lastnode.next !=null){
currnode = currnode.next;
lastnode = lastnode.next;
}
currnode.next = null;//letting 2nd last node point towards null
}
Code:
class LinkedLst{
Node head;
///creating class named as LinkedLst
class Node{
String data; //initializing data
Node next; //initializing next
Node headNode;
Node(String data){
this.data = data; //declaring data
this.next=null; //declaring next as null since last value always points to null
}
}
public void addfront(String data){
Node newnode = new Node(data);//declaring the data given as node
if(head == null){ //corner case: if no value in list, make it the first value
head = newnode;
return;
}
newnode.next = head; //pointinhg our data to the head, so the real head will become 2nd vlue
head = newnode; //making our new data as head // cancelling the pointer of head and making it to point at new node
}
public void extnd(String data){
Node newnode = new Node(data);//declaring the data given as node
if(head == null){ //corner case: if no value in list, make it the first value
head = newnode;
return;
}
node currnode = head; //for iterating. so that actual head value won't change
while(currnode.next != null){ //whether next value is null
currnode = currnode.next; //iterate
}
currnode.next = newnode; //pointing last node towards new node
}
public void delfst(){
if(head == null){ //corner case: if no value in list
System.out.println("empty list");
return;
}
head = this.head.next; //making 2nd value as head
}
public void dellst(){
if(head == null){ //corner case: if no value in list
System.out.println("empty list");
return;
}
currnode = head; //to iterate. this will search secondlast node
lastnode = head.next; //to get last node
while(lastnode.next !=null){
currnode = currnode.next;
lastnode = lastnode.next;
}
currnode.next = null;//letting 2nd last node point towards null
}
public void prnt(){
Node currNode = head;
while(currNode != null) {
System.out.print(currNode.data+" -> ");
currNode = currNode.next;
}
System.out.println("null");
return;
}
public static void main(String[] args) {
LinkedLst list = new LinkedLst(); //creating a linkedlist
list.addfront("Hello");
list.addfront(" second Hello");
list.extnd("Hello");
list.extnd(" second Hello");
list.prn
t();
}
}
This was all about Singular LinkedList
In next blog we will dive into Double LinkedList and circular LinkedList.
Comments
Post a Comment