Linked List – Data Structure

Damith
782 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Overview

Singly Linked List is a linear data structure. In a Linked List each node in the list stores data and reference to the next node.

Array Vs Linked List

Arrays also can be used to store linear data. But compare with the Linked List, Arrays have some limitations.

Pros:-

  1. Arrays size is fixed. We must define the size of the array before use it. In Linked List size is dynamic. We can add data as much as we want.
  2. Insertion and Deletion are not expensive compared with the Array. In array need to be moved the elements when inserting or deleting.

Cons:-

  1. Need extra memory space for keeping a reference to next element.
  2. Random access is not allowed.

Implementation

Node class.

class Node{
    Node nextNode;
    int data;
}

Insert new Node into the linked list.

public void insert(int data) {
    //create a new Node and store a data.
    Node node = new Node();
    node.data = data;
    node.nextNode = null;

    //check the head is null or not.
    //if head is null, assign the Node and exit.
    if (this.head == null) {
       head = node;
       return;
    }

    //assign a head into the temp Node and loop it until find the null reference.
    Node tempNode = this.head;
    while (tempNode.nextNode != null) {
       tempNode = tempNode.nextNode;
    }

    //assign new node.
    tempNode.nextNode = node;
}

This is for print the linked list.

public void print() {
    if (this.head == null) {
        return;
    }
    //print all nodes
    Node tempNode = this.head;
    while (tempNode != null) {
        System.out.print(tempNode.data + "->");
        tempNode = tempNode.nextNode;
    }
    System.out.println("NULL");
}

Complete Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Node {
int data;
Node nextNode;
}
class LinkedList {
private Node head;
public void insert(int data) {
//create a new Node and store a data.
Node node = new Node();
node.data = data;
node.nextNode = null;
//check the head is null or not.
//if head is null, assign the Node and exit.
if (this.head == null) {
head = node;
return;
}
//assign a head into the temp Node and loop it until find the null reference.
Node tempNode = this.head;
while (tempNode.nextNode != null) {
tempNode = tempNode.nextNode;
}
//assign new node.
tempNode.nextNode = node;
}
public void print() {
if (this.head == null) {
return;
}
//print all nodes
Node tempNode = this.head;
while (tempNode != null) {
System.out.print(tempNode.data + "->");
tempNode = tempNode.nextNode;
}
System.out.println("NULL");
}
}
public class Main {
public static void main(String[] args) {
LinkedList ls = new LinkedList();
ls.insert(10);
ls.insert(20);
ls.insert(30);
ls.print();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Original post http://mydevgeek.com/linked-list-data-structure/.

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content