Introduction to Singly Linked List
Singly Linked List is a variant of Linked List which allows only forward traversal of linked lists. This is a simple form, yet it is effective for several problems such as Big Integer calculations.
A singly linked list is made up of nodes where each node has two parts:
- The first part contains the actual data of the node
- The second part contains a link that points to the next node of the list that is the address of the next node.
The beginning of the node marked by a special pointer named START. The pointer points to the fist node of the list but the link part of the last node has no next node to point to.
The main difference from an array is:
- Elements are not stored in contiguous memory locations.
- Size of Linked List need not be known in advance. It can increase at runtime depending on number of elements dynamically without any overhead.
In Singly Linked List, only the pointer to the first node is stored. The other nodes are accessed one by one.
To get the address of ith node, we need to traverse all nodes before it because the address of ith node is stored with i-1th node and so on.
Linked List | Set 2 [Inserting a node]
We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of linked list.
|
// A linked list node
class Node
{
public:
int data;
Node *next;
};
// This code is contributed by rathbhupendra
|
|
// A linked list node
struct Node
{
int data;
struct Node *next;
};
|
|
// Linked List Class
class LinkedList
{
Node head; // head of list
/* Node Class */
class Node
{
int data;
Node next;
// Constructor to create a new node
Node[int d] {data = d; next = null; }
}
}
|
|
# Node class
class Node:
# Function to initialize the node object
def __init__[self, data]:
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class
class LinkedList:
# Function to initialize the Linked List object
def __init__[self]:
self.head = None
|
|
/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node[int d] {data = d; next = null; }
}
|
|
// Linked List Class
var head; // head of list
/* Node Class */
class Node {
// Constructor to create a new node
constructor[d] {
this.data = d;
this.next = null;
}
}
// This code is contributed by todaysgaurav
|
In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1] At the front of the linked list
2] After a given node.
3] At the end of the linked list.