I am working on a project for my Data Structures class that asks me to write a class to implement a linked list of ints.
- Use an inner class for the Node.
- Include the methods below.
- Write a tester to enable you to test all of the methods with whatever data you want in any order.
I have a method called "public void insertAt(int index, int item)". This method is meant to "Insert an item at position index, where index is passed to the method" I have my code for this method down below. When I insert an Item at an Index it works unless it's the first item in the list. When I try to insert an item at the front of the list nothing is added to the list. For example, If I had a list: "[9, 8, 15, 7, 5, 15, 19, 6, 19, 2]" and I want to insert the number "90" and the first index it should look like [90, 9, 8, 15, 7, 5, 15, 19, 6, 19, 90] but instead I get [9, 8, 15, 7, 5, 15, 19, 6, 19, 90]. How can I fix this in my code so if I was to insert an item at the tail it would move the Item I want inserted to be placed before the tail?
import java.util.Random;
import java.util.Scanner;
public class LinkedListOfInts {
Node head;
Node tail;
private class Node {
int value;
Node nextNode;
public Node(int value, Node nextNode) {
this.value = value;
this.nextNode = nextNode;
}
}
public LinkedListOfInts(LinkedListOfInts other) {
Node tail = null;
for (Node n = other.head; n != null; n = n.nextNode) {
if (tail == null)
this.head = tail = new Node(n.value, null);
else {
tail.nextNode = new Node(n.value, null);
tail = tail.nextNode;
}
}
}
public LinkedListOfInts(int[] other) {
Node[] nodes = new Node[other.length];
for (int index = 0; index < other.length; index ) {
nodes[index] = new Node(other[index], null);
if (index > 0) {
nodes[index - 1].nextNode = nodes[index];
}
}
head = nodes[0];
}
public LinkedListOfInts(int N, int low, int high) {
Random random = new Random();
for (int i = 0; i < N; i )
this.addToFront(random.nextInt(high - low) low);
}
public void addToFront(int x) {
head = new Node(x, head);
}
public void insertAt(int index, int item) {
Node temp = head;
Node prev = null;
int i = 0;
for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
if (temp != null) {
prev = temp;
temp = temp.nextNode;
i ;
}
if (index > i) {
prev = temp;
temp = temp.nextNode;
i ;
}
if (index == i) {
Node newItem = new Node(item, null);
prev.nextNode = newItem;
newItem.nextNode = temp;
}
}
}
public String toString() {
String result = "";
for (Node ptr = head; ptr != null; ptr = ptr.nextNode) {
if (!result.isEmpty()) {
result = ", ";
}
result = ptr.value;
}
return "[" result "]";
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
LinkedListOfInts list = new LinkedListOfInts(10, 1, 20);
boolean done = false;
while (!done) {
System.out.println("1. Insert At");
System.out.println("2. toString");
switch (input.nextInt()) {
case 1:
System.out.println("Insert an Item to a certain Index on the List");
list.insertAt(input.nextInt(), input.nextInt());
break;
case 2:
System.out.println("toString");
System.out.println(list.toString());
break;
}
}
}
}
CodePudding user response：
Please read this implementation:
public class LinkedList<T> {
private Node<T> first;
private Node<T> last;
private int counter;
private class Node<T> {
T data;
Node<T> next;
Node<T> prev;
Node(Node<T> prev, T data, Node<T> next) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
private void insertFirst(T s) {
insertAt(0, s);
}
public LinkedList<T> insertAt(int index, T elem) {
if (index > counter) {
throw new IndexOutOfBoundsException();
}
Node<T> node = new Node<T>(null, elem, null);
if (counter == 0) {
first = last = node;
} else {
if (index == 0) {
node.next = first;
first.prev = node;
first = node;
} else if (index == counter) {
node.prev = last;
last.next = node;
last = node;
} else {
Node<T> current = this.first;
for (int i = 0; i < index; i ) {
current = current.next;
}
node.next = current;
node.prev = current.prev;
current.prev.next = node;
current.prev = node;
}
}
counter ;
return this;
}
}
Note the usage of the "counter" field. It stores the number of items in the LinkedList, and is used in the insertAt method. The method takes in consideration, if the index is valid or not, if list has items or not, if the index we want to insert is the head/tail or other index. At the end the counter is also incremented.
CodePudding user response：
You have an error in this line:
if (temp.nextNode != null) {
newItem.nextNode = temp;
}
Right there, temp is your last element, be it 2. Your new element ( 90) will only have temp assigned, it temp has a pointer to the next element (temp.nextNode != null) Because temp has no next element, nextNode won't be assigned at all. In fact, you can omit this check at all cause if temp was null , you would only assign null to the nextNode of the newItem which would be fine.
Also, make sure to handle other issues in your implementation, such as adding the element at index 0. At the moment, you don't handle the situation when prev is null and you would end up with the NPE whenever you try to add the element at index 0.
Writing good unit tests may help you with the robust implementation and will help you solve this kind of issues much quicker. Check out this question to see how to write unit tests in java.