Complete LinkedList


Collapse Content

Other LinkedList Methods

There are still 3 methods that need to be implemented to be a full List:

  • add(index, item) Add an item to a specific location in the list.
  • remove(index) - Remove an item from a specific location in the List.
  • size() - Return the number of elements in the list.

To remove an item or add an item at a specific index, you need to get the Node before that index. You can then change its pointer to the Node after the removed one, or to the Node that's being inserted.

LinkedList Efficiency

To access an item at a specific index, The LinkedList needs to run through all the nodes until that index. It needs to go through half the list on average to add, get or remove items, so it's running time is linear, or directly proportional to its size.

LinkedList in Java

The LinkedList class in Java implements the List interface. This means you can declare a number List with:

 List<Integer> list = new LinkedList<Integer>();

This could later be swapped with an ArrayList without affecting other code. In this challenge you should use your own LinkedList class.

Challenge

Implement the following two methods in your own LinkedList class:

  • add(index, item) Add an item to a specific location in the list.
  • remove(index) - Remove an item from a specific location in the List.

You should also implement the size method and a private helper method getNode(int index) to return the Node at a specific index.

Input and Output

The input will consist of the number t followed by t lines with 1 pair of numbers on each line.

You should have already completed these two methods in the previous challenge:

  • add(num) represented by -9 n in input. Add n to the end of your LinkedList when a -9 appears.
  • get(index) represented by -6 n in input. Get and print the number located at index n whenever a -6 appears.

Create the following two additional methods for this challenge:

  • add(index, item) represented by 2 numbers a b in the input. The first number a will be a positive integer that represents the index where you should insert the second number b.
  • remove(index) represented by -1 n in the input. Remove a number from index n in the list and print its (integer) value.

(Print each number on its own line.)

Sample Input

10
-9 3
-9 5
1 11
2 13
-6 1
-6 3
-1 2
-1 0
-1 1
-6 0

Sample Output

11
5
13
3
5
11

Explanation

See the input, list and output for each step in the table below. Note the new methods in use. For example, the 3rd operation adds the number 11 to the 1th position in the list, and the 5th operation removes and prints the same 11 from position 1.

input current list output
-9 3 3
-9 5 3 5
1 11 3 11 5
2 13 3 11 13 5
-6 1 3 11 13 5 11
-6 3 3 11 13 5 5
-1 2 3 11 5 13
-1 0 11 5 3
-1 1 11 5
-6 0 11 11

Challenge

Create the LinkedList class methods as described above.
(Modify your code from the previous challenge to solve this challenge.)

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Comments

  • Hello guys, I'm using the java.util.LinkedList implementation and it doesn't give the 'correct' output you are putting here, my implementation of LinkedList does the same output as java.util.LinkedList, are you sure the 'correct' output is correct at all? Thanks for this nice web page.

  • Your code needs to handle the different input formats correctly. There are 2 new formats for this challenge: -1 n should remove a number at index n, and 2 positive numbers a b means insert b at index a.

  • Is there a featured awnser here. I would really like to be able to see the awnsers. I only get nullpointexceptions. How can i see the featered awnser if there is one, before i solve this. cause i dont think i can solve this.

  • my code

    Really what am i doing wrong?? It says main.java54 nullpointer but rule 54 is the same as in the previous excersise. Can i just get the awnser please.

  • 54 means the error happened at line 54 in your code. Go there to fix it. nullpointer means you tried doing something with a null value.

  • Yes, i now rule/line 54 but here was nothing wrong there. it was the same as in the previous excersice strange but i had some help already thank you.

  • 10th step is supposed to remove the number 5 which will be in 2th position. Not sure how will it get printed after 14. I get the out pust as 3
    11
    14
    7
    7
    10
    3
    2

  • @senthil, you might want to read again the requirement/instruction for the remove(index) method, the answer to your question is in there.

Contact Us
Sign in or email us at [email protected]