CC-1 : Implement SingleLinkedList.
Description:
Create and test a SingleLinkedList implementation.
SingleLinkedList.
SingleLinkedList consists of list of nodes, where each node has a single link pointing to next node. The structure of a SingleLinkedList Node is shown below. The image shows an integer stored as data in the node of the SingleLinkedList node, but you can store any other data type such characters, strings, objects etc. as data in the node. In a SingleLinkedList, nextNode pointing to null indicates that we have reached the last node of the SingleLinkedList. In the image, as the first node is the only node in the list, the nextNode link will point to null indicating there are no further nodes. The nextNode member variable of the node will point to the next node, if there is a next node or else it will point to null.
11 -> null
Below is the code for the SingleLinkedListNode java class:
public class SingleLinkedListNode implements Node {
private SingleLinkedListNode nextNode=null;
private int nodeData=0;
public SingleLinkedListNode getNextNode() {
return nextNode;
}
public void setNextNode(SingleLinkedListNode nextNode) {
this.nextNode = nextNode;
}
public int getNodeData() {
return nodeData;
}
public void setNodeData(int nodeData) {
this.nodeData = nodeData;
}
}
Besides SingleLinkedListNode class shown above we also need a class named SingleLinkedList that contains a reference to the firstNode of the Single Linked List. Whenever we need to access the data nodes in the LinkedList, we will start from the firstNode and then traverse the whole list using nextNode links. The SingleLinkedListNode class also contains all the code to add/delete/access/traverse the LinkedList nodes (partial code snapshot of the SingleLinkedList is given below):
public class SingleLinkedList {
private SingleLinkedListNode firstNode=null;
public SingleLinkedListNode getFirstNode() {
return firstNode;
}
public void setFirstNode(SingleLinkedListNode firstNode) {
this.firstNode = firstNode;
}
public boolean addLast(int data){
...
}
public boolean addFirst(int data){
...
}
public boolean add(int data, int pos)
{
...
}
public int getSize() {
...
}
public boolean removeFirst() {
...
}
public boolean removeLast() {
...
}
public boolean remove(int data){
...
}
public boolean removeAtPos(int pos){
...
}
public int get(int idx) {
...
}
public void traverse() {
...
}
}
Addition of node to end of SingleLinkedList.
Pseudocode:
| To handle addition of a newNode to end of a SingleLinkedList, we need to handle 2 cases: |
| If the SingleLinkedList is empty, add the newNode as the firstNode of the SingleLinkedList. |
| If the SingleLinkedList already has nodes:
Find the last node of the SingleLinkedList and add the newNode as the nextNode of this last node.
|
Code:
public boolean addLast(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
return true;
}
else {
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=null) {currentNode=currentNode.getNextNode();}
currentNode.setNextNode(node);
node.setNextNode(null);
return true;
}
}
Addition of node to start of SingleLinkedList.
Pseudocode:
| To handle addition of newNode to start of a SingleLinkedList, we need to handle 2 cases: |
| If the SingleLinkedList is empty, add newNode as the firstNode of the SingleLinkedList. |
| If the SingleLinkedList already has nodes:
Set nextNode variable of the newNode to current firstNode of the SingleLinkedList.
Set newNode as the firstNode of the SingleLinkedList.
|
Code:
public boolean addFirst(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(null);
return true;
}
else {
node.setNextNode(firstNode);
firstNode=node;
return true;
}
}
Addition of node to required index in the SingleLinkedList.
Pseudocode:
| To handle addition of a newNode to index pos of a SingleLinkedList, we need to handle 3 cases: |
| If pos is 0 add newNode to start of SingleLinkedList. |
| If pos is equal to number of nodes in the SingleLinkedList, then add new node to end of the SingleLinkedList. |
| If pos is an intermediate index:
Identify the node prevNode at position pos-1.
Set nextNode of newNode to nextNode of prevNode.
Set nextNode of prevNode to newNode.
|
Code:
public boolean add(int data, int pos)
{
int size=getSize();
if ((pos<0) || (pos > size)) { return false;}
if (pos==0) {
addFirst(data);
return true;
}
if (pos==size) {
addLast(data);
return true;
}
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
while (currentNode !=null) {
if ((idx==pos)){
node.setNextNode(prevNode.getNextNode());
prevNode.setNextNode(node);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
}
return false;
}
Deletion of first node of SingleLinkedList.
Pseudocode:
| To handle deletion of firstNode of SingleLinkedList, we need to handle 2 cases: |
| If the SingleLinkedList has only one node, the set firstNode variable of SingleLinkedList to null. |
| If the SingleLinkedList already has more than 1 nodes:
Set firstNode of SingleLinkedList to firstNode.nextNode.
|
Code:
public boolean removeFirst() {
if (firstNode == null) { return false; }
if (firstNode.getNextNode()==null) {
firstNode=null;
return true;
}
firstNode=firstNode.getNextNode();
return true;
}
Deletion of last node of SingleLinkedList.
Pseudocode:
| To handle deletion of last node of SingleLinkedList, we need to handle 2 cases: |
| If the SingleLinkedList already has more than 1 nodes: |
| If the SingleLinkedList already has more than 1 nodes:
Find the second last node of the SingleLinkedList and store its reference in prevNode.
Set prevNode.nextNode to null.
|
Code:
public boolean removeLast() {
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
while (currentNode !=null) {
if (currentNode.getNextNode()==null) {
if (prevNode==null) {
firstNode=null;
return true;
}
prevNode.setNextNode(null);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
}
return false;
}
Delete node at particular index in the SingleLinkedList.
Pseudocode:
| To handle deletion of a node from index pos of a SingleLinkedList, we need to handle 3 cases: |
| If pos is 0, remove the firstNode of SingleLinkedList. |
| If pos is equal to number of nodes in the SingleLinkedList, then remove the last node of the SingleLinkedList. |
| If pos is an intermediate index:
Identify the node prevNode at position pos-1.
Identify the node currentNode at position pos.
Set prevNode.nextNode to currentNode.nextNode.
|
Code:
public boolean removeAtPos(int pos){
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
while (currentNode !=null) {
if (idx==pos) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==null) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
}
return false;
}
Accessing a node at a particular index in the SingleLinkedList.
Pseudocode:
| To access a node at particular index, use the nextNode link to traverse through the SingleLinkedList till the required node is reached. |
Code:
public int get(int idx) {
SingleLinkedListNode currentNode=firstNode;
int currIdx=0;
while (currentNode !=null) {
if (currIdx==idx) {return currentNode.getNodeData();}
currentNode=currentNode.getNextNode();
currIdx++;
}
return Integer.MIN_VALUE;
}
Accessing/ printing the nodes of the SingleLinkedList.
Pseudocode:
| The nextNode link of each node can be used to traverse the nodes of the SingleLinkedList. |
Code:
public void traverse() {
SingleLinkedListNode currentNode=firstNode;
while (currentNode !=null) {
System.out.println(currentNode.getNodeData());
currentNode=currentNode.getNextNode();
}
}
Click here to download and run code and test cases !
| About Us | Privacy Policy | Contact us |