DSA_Linked List

Linked List

An array is a very useful data structure provided in programming languages.

It has at least two limitations:

 (1) changing the size of the array requires creating a new array and then copying

all data from the array with the old size to the array with the new size.

 (2) The data in the array are next to each other sequentially in memory, which

means that inserting an item inside the array requires shifting some other data in

this array.

 These limitations can be overcome by using linked structures.

Ø  A linked structure is a collection of nodes storing data and links to other nodes.

Ø  In this way, nodes can be located anywhere in memory, and passing from one node of the linked structure to another is accomplished by storing the reference(s) to other node(s) in the structure

Singly linked lists

Ø  If a node contains a data field that is a reference to another node, then many nodes can be used together using only one variable to access the entire sequence of nodes.

Ø  Such a sequence of nodes is the most frequently used implementation of a linked list, which is a data structure composed of nodes, each node holding some information and a reference to another node in the list.

Ø  If a node has a link only to its successor(next) in this sequence, the list is called a singly linked list.

Ø  Note that only one variable p is used to access any node in the list.

Ø  The last node on the list can be recognized by the null reference field.

Doubly Linked Lists

Each node has a reference or pointer back to the previous nodes

Implementation of Doubly linked list

public class IntDLLNode {

public int info;

public IntDLLNode next, prev;

public IntDLLNode (int el) {

this (el,null,null);

}

public IntDLLNode (int el, IntDLLNode n, IntDLLNode p) {

info = el; next =n; prev=p;

}

}

public class IntDLList {

private IntDLLNode head, tail;

public IntDLList ( ) {

head = tail = null;

}

public boolean isEmpty( ) {

return head == null;

}

public void addToTail (int el) {

if (!isEmpty ( )) {

tail = new IntDLLNode (el, null, tail);

tail.prev.next = tail; }

else{

 head = tail = new IntDLLNode(el);

}

public int removeFromTail ( ) {

int el = tail.info;

if (head == tail) // if only one node in the list;

head = tail =null;

else { // if more than one node in the list;

tail = tail.prev;

tail.next = null; }

return el;

}

}

2D array

class Testarray3{  

public static void main(String args[]){  

  

//declaring and initializing 2D array  

int arr[][]={{1,2,3},{2,4,5},{4,4,5}};  

  

//printing 2D array  

for(int i=0;i<3;i++){  

 for(int j=0;j<3;j++){  

   System.out.print(arr[i][j]+" ");  

 }  

 System.out.println();  

}  

  

}}  

  

Linked List

An array is a very useful data structure provided in programming languages.

It has at least two limitations:

 (1) changing the size of the array requires creating a new array and then copying

all data from the array with the old size to the array with the new size.

 (2) The data in the array are next to each other sequentially in memory, which

means that inserting an item inside the array requires shifting some other data in

this array.

 These limitations can be overcome by using linked structures.

Ø  A linked structure is a collection of nodes storing data and links to other nodes.

Ø  In this way, nodes can be located anywhere in memory, and passing from one node of the linked structure to another is accomplished by storing the reference(s) to other node(s) in the structure

Singly linked lists

Ø  If a node contains a data field that is a reference to another node, then many nodes can be used together using only one variable to access the entire sequence of nodes.

Ø  Such a sequence of nodes is the most frequently used implementation of a linked list, which is a data structure composed of nodes, each node holding some information and a reference to another node in the list.

Ø  If a node has a link only to its successor(next) in this sequence, the list is called a singly linked list.

Ø  Note that only one variable p is used to access any node in the list.

Ø  The last node on the list can be recognized by the null reference field.

Doubly Linked Lists

Each node has a reference or pointer back to the previous nodes

Implementation of Doubly linked list

public class IntDLLNode {

public int info;

public IntDLLNode next, prev;

public IntDLLNode (int el) {

this (el,null,null);

}

public IntDLLNode (int el, IntDLLNode n, IntDLLNode p) {

info = el; next =n; prev=p;

}

}

public class IntDLList {

private IntDLLNode head, tail;

public IntDLList ( ) {

head = tail = null;

}

public boolean isEmpty( ) {

return head == null;

}

public void addToTail (int el) {

if (!isEmpty ( )) {

tail = new IntDLLNode (el, null, tail);

tail.prev.next = tail; }

else{

 head = tail = new IntDLLNode(el);

}

public int removeFromTail ( ) {

int el = tail.info;

if (head == tail) // if only one node in the list;

head = tail =null;

else { // if more than one node in the list;

tail = tail.prev;

tail.next = null; }

return el;

}

}

2D array

class Testarray3{  

public static void main(String args[]){  

  

//declaring and initializing 2D array  

int arr[][]={{1,2,3},{2,4,5},{4,4,5}};  

  

//printing 2D array  

for(int i=0;i<3;i++){  

 for(int j=0;j<3;j++){  

   System.out.print(arr[i][j]+" ");  

 }  

 System.out.println();  

}  

  

}}