Lists

Collapse Content Show Content

As mentioned, software's main purpose is to handle data, often collections of similar data. A List is one of the simplest data structures for holding a collection of data.

Abstract Lists

Before describing ways to implement a List, we'll examine what a List is. A List holds a collection of values (or objects) in a specific order, and the same value can occur more than once in the List.

A List should support the following methods:

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

A List lets you repeatedly add items to it without worrying about its size. You can use Lists that support the above operations without knowing how the List is implemented. However, if you know how the Lists work, you can choose the optimal List type for each situation.

LinkedLists

A LinkedList is a series of Nodes where each Node points to the next Node in the List.

Linked List

The LinkedList class contains implementations of the List methods. This lets you use the List class to add, find and remove items without having to deal with the Nodes that the LinkedList uses internally.

Implementing the basic List methods

The LinkedLists needs to keep track of the first Node in the list, so it should keep a head variable. To get an element from the list at index i you start from the head and keep on going to the next Node until you reach that position.

To add an element to the list with value v, you need to create a new Node with that value and then point the previous last Node to the new Node. It makes sense to create a tail variable so the last element can be accesses immediately without going through the entire list.

Challenge

Create your own LinkedList class for storing integers which should include two methods:

add(int num) - this should add a new Node to the end of the list with a value of num
get(int i) - this should return the value of the Node at position i in the List.

For Java and Ruby, you can complete the provided code. For other languages, read the input output details to see how to use your classes to solve the challenge.

Input and Output

The input will consist of the number t followed by t lines with 1 pair of numbers on each line. The first number in each pair is the operation and the second number is the parameter. In this challenge, there are only 2 operations:

add represented by the number -9. Add the given number to the end of your LinkedList when a -9 appears.
get represented by the number -6. Get and print the number located at the given index whenever a -6 appears. (Print the number on its own line.)

Sample Input

Sample Output

5
4
3

The 4 add operations create the following list: {3, 5, 7, 4}.
The 3 get operations get the numbers located at positions 1, 3 and 0.

Challenge

Create a LinkedList as described above.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Previous Next Node

Comments

Sarick Shah

Feb 15, 4:36 PM

public void add(int num){
    head = tail;
    tail.next = new Node(num);
    tail = tail.next;



}

/*
 * Returns value of node at given index

cont...

 */
    public int get(int index){
    temp = head;
    for (int i = 0; i<index; i++){
        temp = temp.next;
    }
    return;
}

}

Sarick Shah
Feb 15, 4:36 PM

what am i supposed to return?
Sarick Shah
Feb 15, 4:38 PM

this is telling me that my return value needs to be an integer, I'm lost
Learneroo
Feb 15, 4:57 PM

@sarah, you can link to long pieces of code so you don't need to paste them here. The method get needs to return an integer (the value or data of a node). See if the new hint helps (or the new cheat option if you need it.)
Sarick Shah
Feb 15, 6:38 PM

thanks, i realize what i was doing wrong.
thales
Aug 3, 3:04 PM

Do i understand it correct if i say that head and tails arent nodes themselves?
Learneroo
Aug 3, 3:08 PM

No, the first node in the list is the head and the last node is the tail. (If there's just one node, it's both the head and tail.)
thales
Aug 3, 3:28 PM

When i state tail is head , can i consider them as one node with 2 names (startingpoint), or are they two different nodes with the same name. In case two i dont understand the line:

cont...
tail.next = node ( i guess this is the connection to the new node)
tail=node ( this is strange, since now tail is my new nood, but the connection is gone, or is in head of??

I dont really get this as you might of guessed while reading my question
thales
Aug 4, 4:44 PM

class LinkedList {
Node head;
Node tail;

So i have two 'dummy' nodes. But what is the data en what is the pointer of head.

if head==0 -------------> what does this mean, what is null, the pointer? Then what is the data?
thales
Aug 5, 11:40 AM

Nevermind, i understand it now. Its cause the default points to null.

Also i understand why i can say tail.next and it does the same for the head. This cause its a reference variable. So i guess i figured it out :-)
catypus
Jun 30, 6:04 AM

Why is it supposed to be
head = tail...
and not
head.next=tail;

THis is driving me nuts! I drew this out on paper TWICE and while I understand the concept... I cant code it!
Learneroo
Jun 30, 8:28 AM

Which part are you referring to? When there's only one item in the list, that item is both the head and the tail. This a correct solution.
oorja
Nov 30, 4:40 AM

is that python 2.6
I am using python 3.5 working ok on my ide but here it is failing on
reading data.
Learneroo
Nov 30, 8:06 AM

Yes it's python 2.

All Node Comments