You are invited to Log in or Register a free Frihost Account!

# Data structures - small question

davidv
Hi, I'm trying to implement a singly LinkedList. I wanted to know, typically are linked lists implemented using an array or is it simply a collection of nodes with references to the next without the use of an array?

I'm doing this in Java and I have to create two add methods (among many others) where one just appends and the other adds say between index 1 and 2. I'm assuming a LL is just a collection of nodes referencing to the next without an array. What's the point of having a next() method when the access time is already O(1) when we know the index... but anyway, how can I implement the add(int ind, Node node) method without the use of an array but still in T(n) = O(1) running time, I could start at the head pointer and then next() to n - 1, however that's T(n) = O(n), right? I'm going to say the Nodes within my LL do not have indices...
Linked lists don't use arrays. To access an element in a linked list if you know the index is O(n) because you will have to traverse the list from the start. You are right that add(int ind, Node node) will have to be O(n). If you already have the node at the index you want to insert after you can make an add O(1).
In C++, std::list has an insert function that takes an iterator and the element to add to the list. This will insert the new element before the element pointed to by the iterator. And it is O(1). I can't see that LinkedList in Java have anything similar but I guess I just don't know where to look.
davidv
 Peterssidan wrote: Linked lists don't use arrays. To access an element in a linked list if you know the index is O(n) because you will have to traverse the list from the start. You are right that add(int ind, Node node) will have to be O(n). If you already have the node at the index you want to insert after you can make an add O(1). In C++, std::list has an insert function that takes an iterator and the element to add to the list. This will insert the new element before the element pointed to by the iterator. And it is O(1). I can't see that LinkedList in Java have anything similar but I guess I just don't know where to look.

Does that mean if the LL doesn't use an array, each node in the LL will need to have an index in order for me to implement to add(int ind, Node node) method along with a reference to the next node?
Often the Node is an implementation detail and is hidden from the user of the linked list. with add(int ind, Node node) you are actually inserting a node? Is this what you want. With a Java LinkedList<E> add looks like this add(int index, E element). see, no node mentioned.

A node in a single linked list only contain the element and a pointer/reference to the next node. If the list is double linked the node also contains a pointer to the previous node.

To find the node at a certain position all you have to do is to count the number of nodes from the start of the list until you reach the correct index.
Fire Boar
Often it's helpful to draw a mental picture of the data structure when thinking about how to implement it. This also helps in deciding which data structure is best for the job.

Singly linked lists are a very efficient data structure that acts like a chain: each element is like a link in the chain. It is good at iteration and insertion/deletion at the ends (assuming you keep a pointer to each end): both of these take constant time per element iterated over/inserted/deleted, which is the most efficient it can possibly be. Conversely, an array is bad at insertion at the front, because you first have to move every element up one slot. Therefore, an array-based implementation would not be an efficient solution.

It's good to know the limitations of your data structure as well. Arrays are great at replacement and direct access (constant time) at an index, while linked lists are not (linear time).
davidv
 Fire Boar wrote: Often it's helpful to draw a mental picture of the data structure when thinking about how to implement it. This also helps in deciding which data structure is best for the job. Singly linked lists are a very efficient data structure that acts like a chain: each element is like a link in the chain. It is good at iteration and insertion/deletion at the ends (assuming you keep a pointer to each end): both of these take constant time per element iterated over/inserted/deleted, which is the most efficient it can possibly be. Conversely, an array is bad at insertion at the front, because you first have to move every element up one slot. Therefore, an array-based implementation would not be an efficient solution. It's good to know the limitations of your data structure as well. Arrays are great at replacement and direct access (constant time) at an index, while linked lists are not (linear time).

Yep, which was exactly what I did. A DLL and SLL or CLL are very simple data structures and I do know how to implement them however I wasn't sure whether or not I should use an array or not but now I do. Thanks for the helpful comments and tips