Hi I am working on implementing a linked list without importing any Java library. I have implemented the following class. I have a couple of test cases to make sure that the linked list object does not change after append and insert which is failing. Can someone look into my code and what do I need to do to make the last two outputs correct? Thank you.
class LinkedList {
LinkedList.Node head = null;
int size = 0;
class Node {
char value;
Node next = null;
public Node(char value){
this.value = value;
this.next = null;
}
public char getValue() {
return value;
}
public void setValue(char value) {
this.value = value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public void concat(LinkedList otherList) {
if (otherList == null) {
return;
}
else if (this.head == null) {
this.head = otherList.head;
size += otherList.size;
} else {
LinkedList.Node current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = otherList.head;
size += otherList.size;
}
}
public LinkedList append(char ch) {
if (head == null) {
head = new Node(ch);
} else {
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = new Node(ch);
}
size++;
return this;
}
public static String toString(LinkedList list) {
String result= "";
int i= 0;
while (i < list.length()) {
result += list.getCharAt(i);
i++;
}
return result;
}
public char getCharAt(int position) throws IndexOutOfBoundsException {
Node current = head;
for(int nodeIndex = 0; nodeIndex < size; nodeIndex++){
if(nodeIndex == position) {
break;
}
else{
current = current.next;
}
}
return current.value;
}
public int length() {
Node temp = head;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
public void insert(int position, char ch) throws IndexOutOfBoundsException {
if (position == size) {
append(ch);
} else if (position > size) {
throw new IndexOutOfBoundsException();
} else {
Node newNode = new Node(ch);
if (head == null) {
head = newNode;
} else if (position == 0) {
newNode.next = head;
head = newNode;
} else {
Node current = head;
Node previous = null;
for (int i = 0; i < position; i++) {
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
size++;
}
}
}
Main Class -> See the last two system out statements where the problem is.
public class Main {
public static void main(String[] args) {
LinkedList list1= new LinkedList();
LinkedList list2= new LinkedList();
list1= list1.append('t').append('i').append('n').append('k').append('e').append('r');
list2= list2.append('b').append('e').append('l').append('l');
System.out.println(LinkedList.toString(list1)); // tinker correct
System.out.println(LinkedList.toString(list2)); // bell correct
list1.concat(list2); // tikerbell correct
System.out.println(LinkedList.toString(list1)); // tinkerbell correct
System.out.println(LinkedList.toString(list2)); // bell correct
list1.append('s'); // make tinkerbell -> tinkerbells
list2.insert(3, 'e'); //bell -> belel
System.out.println(LinkedList.toString(list1)); // printing tinkerbelels - should be tinkerbells - incorrect
System.out.println(LinkedList.toString(list2)); // printing belels - should be belel - incorrect
}
}
Your concat method should not link the first list to the nodes of the second list. Instead it should create new nodes and append those to the first list.
Before dealing with that, first some remarks on your code:
getCharAt is declared as throwing IndexOutOfBoundsException, but it never does.getCharAt and insert have a similar loop to find a node at a given position. This code repetition can be avoided if you would implement a method getNodeAt. Then both getCharAt and insert can use that method. Also the append method can make use of getNodeAt, providing it size-1 as position.size, you shouldn't need the length method.insert is provided with a negative position and the list is not empty, it will throw a null pointer exception, as you will access previous.next while previous is null.toString calls getCharAt repeatedly which makes it inefficient: a list iteration will start for finding each character, which gives it a quadratic time complexity.toString repeatedly creates strings with +=. You can use StringBuffer to avoid this.toString should not be a static method, and should not be called as such from main. toString is supposed to be an instance method.get* and set* methods defined on the Node class. They are therefore not needed.append method to be chainable, by returning the LinkedList instance. Then maybe also make the insert method chainable?Node does not need anything that relates to the LinkedList class, it could be defined as static. And as your LinkedList exposes no Node instances to the outside world (which is good!), the Node class can be private.Here is your code with the above mentioned remarks addressed, and the concat method updated so it creates new nodes for what is in the second list:
import java.util.*;
class LinkedList {
Node head = null;
int size = 0;
private static class Node {
char value;
Node next = null;
public Node(char value) {
this.value = value;
this.next = null;
}
}
private Node getNodeAt(int position) throws IndexOutOfBoundsException {
if (position < 0 || position >= size) {
throw new IndexOutOfBoundsException("Invalid position given to getNodeAt");
}
Node current = head;
while (position-- > 0) {
current = current.next;
}
return current;
}
public LinkedList prepend(char ch) {
Node newNode = new Node(ch);
newNode.next = head;
head = newNode;
size++;
return this;
}
public LinkedList insert(int position, char ch) throws IndexOutOfBoundsException {
if (position == 0) {
return prepend(ch);
}
Node previous = getNodeAt(position - 1);
Node newNode = new Node(ch);
newNode.next = previous.next;
previous.next = newNode;
size++;
return this;
}
public LinkedList append(char ch) {
return insert(size, ch);
}
public String toString() {
StringBuffer result = new StringBuffer();
for (Node temp = head; temp != null; temp = temp.next) {
result.append(temp.value);
}
return result.toString();
}
public char getCharAt(int position) throws IndexOutOfBoundsException {
return getNodeAt(position).value;
}
public void concat(LinkedList otherList) {
Node tail = head == null ? null : getNodeAt(size - 1);
for (Node current = otherList.head; current != null; current = current.next) {
if (head == null) {
tail = head = new Node(current.value);
} else {
tail = tail.next = new Node(current.value);
}
}
size += otherList.size;
}
}
The main function should also change, so it doesn't call toString as a static method:
public class Main {
public static void main(String[] args) {
LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();
list1= list1.append('t').append('i').append('n').append('k').append('e').append('r');
list2= list2.append('b').append('e').append('l').append('l');
System.out.println("" + list1); // tinker
System.out.println("" + list2); // bell
list1.concat(list2); // tikerbell
System.out.println("" + list1); // tinkerbell
System.out.println("" + list2); // bell
list1.append('s'); // make tinkerbell -> tinkerbells
list2.insert(3, 'e'); //bell -> belel
System.out.println("" + list1); // tinkerbells
System.out.println("" + list2); // belel
}
}