Linked List Implementation
To represent a Node, we define a class Node. The following methods are defined inside the LinkedList class and DoublyLinkedList class:
- insertAtBegin(int value): Inserts a node at the beginning of the list with given value.
- insertAtEnd(int value): Inserts a node at the end of the list with given value.
- insert(int value, int nodeNum): Inserts a node at the the specified position of the list with given value.
- deleteAtBegin(): Removes a node from the beginning of the list
- deleteAtEnd(): Removes a node from the end of the list.
- delete(int nodeNum): Deletes a node from the the specified position of the list.
- show(): Prints the complete list.
Additionally, the LinkedList class also defines a method to reverse the list and the DoublyLinkedList class defines a method to print the list in reverse order.
Singly Linked List
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
class LinkedList {
Node head;
int nodes;
LinkedList() {
this.head = null;
nodes = 0;
}
boolean insertAtBegin(int value) {
Node node = new Node(value);
if (head != null)
node.next = head;
head = node;
nodes++;
return true;
}
boolean insertAtEnd(int value) {
Node temp = head;
Node node = new Node(value);
if (head == null)
head = node;
else {
while (temp.next != null)
temp = temp.next;
temp.next = node;
}
nodes++;
return true;
}
boolean insert(int value, int nodeNum) {
if (nodeNum < 1 || nodeNum > nodes + 1)
return false;
else if (nodeNum == 1) {
if (insertAtBegin(value))
return true;
return false;
}
Node node = new Node(value);
Node temp = head;
int pos = 1;
while (pos < nodeNum - 1) {
temp = temp.next;
pos++;
}
node.next = temp.next;
temp.next = node;
nodes++;
return true;
}
boolean deleteAtBegin() {
if (head == null)
return false;
Node temp = head;
head = temp.next;
temp.next = null;
nodes--;
return true;
}
boolean deleteAtEnd() {
if (head == null)
return false;
Node temp = head;
if (temp.next == null) {
head = null;
nodes--;
return true;
}
while (temp.next.next != null)
temp = temp.next;
temp.next = null;
nodes--;
return true;
}
boolean delete(int nodeNum) {
if (nodeNum < 1 || nodeNum > nodes)
return false;
else if (nodeNum == 1) {
if (deleteAtBegin())
return true;
return false;
}
Node temp = head;
int pos = 1;
while (pos < nodeNum - 1) {
temp = temp.next;
pos++;
}
temp.next = temp.next.next;
nodes--;
return true;
}
void reverse() {
Node prevNode = null;
Node currentNode = head;
Node nextNode;
while (currentNode != null) {
nextNode = currentNode.next;
currentNode.next = prevNode;
prevNode = currentNode;
currentNode = nextNode;
}
head = prevNode;
}
void show() {
Node temp = head;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
}
Doubly Linked List
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
prev = null;
next = null;
}
}
class DoublyLinkedList {
Node head;
int nodes;
DoublyLinkedList() {
head = null;
nodes = 0;
}
void insertAtBegin(int value) {
Node node = new Node(value);
if (head != null) {
node.next = head;
head.prev = node;
}
head = node;
nodes++;
}
void insertAtEnd(int value) {
Node temp = head;
Node node = new Node(value);
if (head == null)
head = node;
else {
while (temp.next != null)
temp = temp.next;
temp.next = node;
node.prev = temp;
}
nodes++;
}
void insert(int value, int nodeNum) {
if (nodeNum < 1 || nodeNum > nodes + 1)
return;
else if (nodeNum == 1) {
insertAtBegin(value);
return;
} else if (nodeNum == nodes + 1) {
insertAtEnd(value);
return;
}
Node node = new Node(value);
Node temp = head;
int pos = 1;
while (pos < nodeNum - 1) {
temp = temp.next;
pos++;
}
node.prev = temp;
(temp.next).prev = node;
node.next = temp.next;
temp.next = node;
nodes++;
}
void deleteAtBegin() {
Node temp = head;
if (head == null)
return;
else if(head.next != null){
head.prev = null;
}
head = temp.next;
temp.next = null;
nodes--;
}
void deleteAtEnd() {
if (head == null)
return;
Node temp = head;
if (temp.next == null) {
head = null;
nodes--;
return;
}
while (temp.next.next != null)
temp = temp.next;
temp.next.prev = null;
temp.next = null;
nodes--;
}
void delete(int nodeNum) {
if (nodeNum < 1 || nodeNum > nodes)
return;
else if (nodeNum == 1) {
deleteAtBegin();
return;
}
else if(nodeNum == nodes){
deleteAtEnd();
return;
}
Node temp = head;
int pos = 1;
while (pos < nodeNum - 1) {
temp = temp.next;
pos++;
}
temp.next.next.prev = temp;
temp.next.prev = null;
temp.next = temp.next.next;
nodes--;
}
void show() {
Node temp = head;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
void reverseOrder() {
Node temp = head;
while (temp.next != null)
temp = temp.next;
while (temp != null) {
System.out.println(temp.data);
temp = temp.prev;
}
}
}
Comments
Post a Comment