6

In Java, I have been asked to store integer values in a singly-linked list and then print the elements stored in the list. Here is what I came up with:

int max = 10;
List<Integer> list = new ArrayList<Integer>();

for (int num = 0; i < max; i++){
     list.add(num);
}
System.out.print(list);

I was wondering, is ArrayList the same thing as a singly-linked list? I want to make sure that I'm answering the question correctly. Does this make sense? Thanks!

6 Answers 6

5

No - ArrayList is not a linked list at all - it's an array list. ArrayList stores its elements in an array, whereas linked lists store them in arbitrary memory by linking objects together.

LinkedList is a doubly-linked list, and I'm sure that there are various singly linked list implementations you could grab, but given that this is an assignment you'll either be marked down or fail outright if you try to hand in code using someone else's implementation.

Instead, find an article etc. which describes linked lists and try to implement one yourself.

Generally these are built in java by having a class SomeClass containing a forward link of type SomeClass and a value. You build the list by linking each SomeClass instance to the next through the forward link.

0
2

No ArrayList is definitely not the same as a singly linked list. In fact, it is not a linked list at all: it is a list that uses an array for its backing storage. This lets you access ArrayList in arbitrary order, as opposed to linked lists, that must be accessed sequentially.

Java library has a doubly-linked list, but no singly-linked one; you need to write it yourself.

There are several good implementations available on the internet; take a look at this answer on the codereview site to gain some ideas on how to implement a singly linked list of your own.

1

No, ArrayList is an implementation of the List interface that uses a backing array to store the data. It sounds like the assignment wants you to write your own singly-linked List implementation.

1

No, an ArrayList is backed by an array. Arrays utilize contiguous storage (that is, the start of the array + offset of size of whatever is stored in the array == next element). Java has a LinkedList class, however, this is a doubly linked list, meaning that it contains two references: one to the previous element, and one to the next element.

Java does not have a singly linked list as a built in data structure. Either the question is asking you write your own implementation of a singly linked list, or is incorrect when it says to use one.

1

The name "Array"List states that the underlying implementation uses "arrays" for management. Whenever we talk about "Linked"List we are actually thinking about "Noded" lists i.e. every element has got a pointer to the forward node (and previous node if doubly-linked list). At least that's what this DSA book (by Granville Barnett and Luca Del Tongo) is saying.

0

In commercial Life your Solution is Perfect, but unfortunately ist seems that you are requested to use a Single linkes List which in Std Java does Not exist. (And would Not make much sense) For Purpos of Training you have to Write your own List.

4
  • Out of curiosity, why do you say that a singly linked list does not make sense in java?
    – Jeff
    Commented Dec 13, 2012 at 2:11
  • @Jeff ArrayList internally uses memcopy which makes it faster than linkedlist for all operations, even at delete where linked should be faster by theory but is not.
    – AlexWien
    Commented Dec 13, 2012 at 12:29
  • Ah, I see what you mean. I thought you were saying that there was some reason why singly linked lists were somehow innately illogical in java.
    – Jeff
    Commented Dec 13, 2012 at 19:40
  • @jeff yes it was a bit of a hidden gem in that sentence
    – AlexWien
    Commented Dec 13, 2012 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.