Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[MadocComadrin]

ArrayLists are fast to get data out of, and has less overhead.
LinkedLists are fast to get data into, and has more overhead.

To elaborate on this:
ArrayLists are based on arrays: you can access data via an index in constant time, however, adding to anywhere but the end requires shuffling the rest of the elements around, which takes linear time. Likewise, once the array they are based on runs out of room, they need to create a bigger one and copy the old data into it (or if you're lucky, some languages can extend the array if there's room on the heap).

LinkedLists are based on nodes of elements linked to each other via pointers. They can grow and shrink nearly effortlessly, as adding an element at any known point is simply creating a new node and updating the neighboring links, which ends up being constant time. They are not good for accessing data via position, as indices are not stored or implied anywhere: that means doing so is linear time. LinkedLists make great basic queues and stacks.

The memory overhead is slightly larger for LinkedList, as they need to store a pointer for each element, but on most machines this is trivial (assuming you have good garbage collection/created the "gang of three" correctly).

All in all, for your problem, you could use either with proper practice. I like linked-lists myself.

Code: [Select]

for(String s : names)
bit, though. Only syntax they ever put us through was

Code: [Select]

for(initial state; termination state; change after each iteration)
If that format makes any sense.

Aye, both are valid. The former is often called the "enhanced for-loop" (although IMHO, both have their uses), and is used to iterate over collections in a much more readable manner.
In general, its syntax looks like this in Java.

Code: [Select]

for(ElementType e : myCollection)You then can use "e" within the body of the for loop to retrieve data from the current element (and sometimes modify it).

[Max White]

I have my hands full at the moment, so can't really delve in too deep. Stargazer, where the hell are you? This is totally your thing! I thought we had a truce, a truuuce!

Anyway, some of the basics!

Code: [Select]

LinkedList<type> name= new LinkedList<type>();This will make a new linked list of what ever type you put between the <>

Code: [Select]

list.add(object);This will add the item to the end of the list.

Code: [Select]

list.get(int)This will get the item at the specific index. It is what lists use to get data out, while arrays use the following instead

Code: [Select]

array[int]

[Bauglir]

Seems legit. Since, now that I know what you mean by "know in advance", I can safely say I do know that, I'll probably stick with arrays for these shenanigans (since the code already runs), but learning new things is always good!

Thanks for the help.

[SolarShado]

A common recommendation is declare your lists as such:

Code: [Select]

List<String> myList = new ArrayList<String>();

Notice the type of myList? It's the interface List instead of a specific implementation. This way if you need to change between using an ArrayList and a LinkedList you only need to change a single line of code.

[Nadaka]

RAAA!

Weblogic isn't picking up my struts 2 @action annotations. There is literally no reason for this to not work.

[Stargrasper]

Sorry, I've been busy...

Short Version:
* Use a native array if you know how many elements the list will contain.  You can calculate that at runtime so long as you've figured it out by the time the array is instantiated.
* Use an ArrayList if you need to do a lot of lookups.
* Use a LinkedList if you need to do a lot of adds/removes from the beginning or middle of the list.

Also, to save a few seconds of typing, you can declare lists with diamond operators in Java 7.

Code: [Select]

List<Object> ol = new ArrayList<>();

Depending on what you're doing, though, it's possible none of these three is the best solution.  Would you like me to write a lesson on data structures?

[Doohl]

There's something that's always bugged me about C++...

What's the difference between std::List and std::Vector? They are both dynamic entity containers. When should you use Lists or Vectors?

[kaijyuu]

http://cplusplus.com/reference/stl/list/

http://cplusplus.com/reference/stl/vector/

Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

Compared to arrays, [vectors] provide almost the same performance for these tasks, plus they have the ability to be easily resized. Although, they usually consume more memory than arrays when their capacity is handled automatically (this is in order to accommodate extra storage space for future growth).

Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.

[Stargrasper]

There's something that's always bugged me about C++...

What's the difference between std::List and std::Vector? They are both dynamic entity containers. When should you use Lists or Vectors?

Tangentially related fun fact: In Java, ArrayList and Vector are the same except that Vector is synchronized.

[alway]

There's something that's always bugged me about C++...

What's the difference between std::List and std::Vector? They are both dynamic entity containers. When should you use Lists or Vectors?

http://www.cplusplus.com/reference/stl/
Read up on the stl containers; knowing how to use them can make your programs faster. Particularly as it pertains to Big O Notation.

As for the question, from the list page linked in the above page:

Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

They have insertion and deletion in constant time. Vectors are stored in what is essentially an array; that is to say, a continuous chunk of memory with a length which must be equal to or greater than the number of elements times the size of the elements. If you put more in than it can hold, it requires the vector to: 1. Allocate a chunk of memory capable of holding the entire vector; followed by 2. Copying the entire vector's contents into the newly allocated memory. The amount of time it takes to copy increases linearly with number of elements to insert, with the number of copies increasing linearly to the number of elements to insert, giving a big O notation of O(n) = n^2; as opposed to O(n) = n for the list (constant insert time, number of inserts linear). If you are inserting a million elements, a vector will take on the somewhere around half a dozen orders of magnitude more time; the difference somewhere on the order of completing in a millisecond and completing in several minutes in the case of a million inserts.

Another tip: If you are going into a programming industry, be sure you are an expert in Big O Notation. Each and every technical interview I've had (Microsoft, Zynga, Intel) all had questions about Big O Notations and space/time complexity. It's really important stuff

[SolarShado]

Also, to save a few seconds of typing, you can declare lists with diamond operators in Java 7.

Code: [Select]

List<Object> ol = new ArrayList<>();


O_O
I did not know of this, but have wondered why it wasn't in on multiple occasions.

I'm still working in Java 6, are the bugs worked out of 7 yet? I seem seem to recall hearing of some semi-major ones at first...

[Siquo]

Spoiler: Shit, I did it again (click to show/hide)

I'm still working in Java 6, are the bugs worked out of 7 yet? I seem seem to recall hearing of some semi-major ones at first...

No, it's still Java. 

Anyway, alway is very right. Big O is... quite a basic necessity. Once you have to wait for more than a second to get your result, it's time to get... Efficient. I think the problem is that nowadays there's a lot more power... and that one second is a long way away, so aspiring programmers can get away with a lot more crap.

[Mego]

http://cplusplus.com/reference/stl/list/

http://cplusplus.com/reference/stl/vector/

Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

Compared to arrays, [vectors] provide almost the same performance for these tasks, plus they have the ability to be easily resized. Although, they usually consume more memory than arrays when their capacity is handled automatically (this is in order to accommodate extra storage space for future growth).

Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.

I've been using std::list's and std::vector's for ages, and never thought to consider which would be faster for what. I think I can make a lot of optimizations in various projects I have now.

[Max White]

Although the cool thing about linkedlists is that if you are building your own, you have a lot of options to mess around with. Will it be single or double linked? Linear or circular? Or will you just say fuck it and turn it into a tree structure? The possibilities!

[Willfor]

So I was looking at my outputs from that simulation thingy I've been making off and on, and I noticed something:

Code: (The Yearly Reports from a Settlement and the Top 10 songs of each of its decades) [Select]

Felijar
Reports:
--0--Lawbene Anieli
--1--Lawbene Anieli
--2--Lawbene Anieli
--3--Lawbene Anieli
--4--Lawbene Anieli
--5--Lawbene Anieli
--6--Lawbene Anieli
--7--Lawbene Anieli
--8--Lawbene Anieli
--9--Lawbene Anieli
--10--Lawbene Anieli
**Top10 Songs:
    At The End Of The World With Felifart  by  Sawqui Devmatt
    You Get Me Riled Up Felifart  by  Sawqui Devmatt
    You Get Me Riled Up Felifart  by  Sawqui Devmatt
    You Get Me Riled Up Felifart  by  Sawqui Devmatt
--11--Lawbene Anieli
--12--Lawbene Anieli
--13--Lawbene Anieli
--14--Lawbene Anieli
--15--Lawbene Anieli
--16--Lawbene Anieli
--17--Lawbene Anieli
--18--Lawbene Anieli
--19--Lawbene Anieli
--20--Lawbene Anieli
**Top10 Songs:
    Oh, Rachbene  by  Sawqui Devmatt
    At The End Of The World With Rachbene  by  Sawqui Devmatt
    Debglen Your Heart Can Be Mine  by  Felifart Elglen
    Look Into My Eyes, Debglen  by  Felifart Elglen
    Take Another Piece of my Partner, Debglen  by  Felifart Elglen
    Let's Go Home, Rachbene  by  Sawqui Devmatt
    What a Wonderful Buttercup, Rachbene  by  Sawqui Devmatt
    At The End Of The World With Felifart  by  Sawqui Devmatt
    Felifart Your Heart Can Be Mine  by  Sawqui Devmatt
    You Get Me Riled Up Felifart  by  Sawqui Devmatt
--21--Lawbene Anieli
--22--Lawbene Anieli
--23--Lawbene Anieli
--24--
So in the first decade of the settlement, Sawqui Devmatt was the only musician writing songs worth listening to. He was obviously in a relationship with Felifart, because the only songs that can be generated right now are love songs about people a character is heavily attracted to. Somewhere between year 10 and year 20 they began seeing other people, and as it turns out, Felifart was gifted with the ability to write songs as well. Unfortunately, I don't have the full story between them. Only two people in my more detailed output file ever met Felifart, and it was only in passing in both cases. It's the unfortunate result of having my simulator pick people at random for a more detailed examination.

This is the first time I've had two musicians romantically involved with each other, and I had no idea that this particular output would give me any information on a publicly aired relationship debacle. All I wanted to do was track what imaginary people listened to by decade... I'm rather impressed. And also anticipating that it only rarely ever happens again.