Be the first user to complete this post

  • 0
Add to List
Beginner

16. Singly Linked List Implementation

Linked List- As the name suggests it's a list which is linked.

  • Linked List consist of Nodes

Nodes are nothing but objects of a class and each node has data and a link to the next node.

class Node {
  public int data;
  public Node next;

  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}
Node
  • The last node in the list points to NULL , so when you reach there you will know that the list ends here.
Linked List

Operations:

Add at the Start : Add a node the beginning of the linked list. Its O(1).

Add at the End : Add a node at the end of the linked list. its O(n) since to add a node at the end you need to go till the end of the array.

Delete at the Start : Delete a node from beginning of the linked list. Its O(1).

Delete at the End : Delete a node from the end of the linked list. its O(n) since to delete a node at the end you need to go till the end of the array.

Get Size: returns the size of the linked list.

Get Element at Index : Return the element at specific index, if index is greater than the size then return -1. its O(n) in worst case.

Add Element at Specific Index : Add element at specific index. If index is greater than size then print "INVALID POSITION". Worst case its O(n)

Display(): Prints the entire linked list. O(n).

Output:

->5->10->20->15
Size of the list is: 4
Element at 2nd position : 10
Searching element 20, location : 4