Can someone explain to me....

[Hyperblaze]

The difference between arrays and linked lists?

I've read http://en.wikipedia.org/wiki/Linked_list

but still confused by it.

 

[Nothinman]

With an array you use numbered indexes to access the elements. With a linked list you have to use element->next and in a doubly-linked list element->prev.

To get to element 3 in an array you'd just use array[2], for a linked list you'd have to start at the top and loop over element->next until you got there.

 

[duragezic]

I was gonna try and think hard from my data structurers class, but pretty much everything I was gonna say is under

'Tradeoffs: Arrays vs Linked Lists'


in that Wiki. The big one being arrays are random accessed, linked lists are sequential. So re-read that part. Its a lot to learn and understand from one reading. Or make a simple implementation of each, then'll you have a decent understanding. Theres tons of example code/guide for them. I've found from my CS classes I dont truly understand the topics until the assignment comes and I've been fvcking around for hours trying to get the damn thing to work.

 

[cleverhandle]

Just restating what the others have said:

In an array, you find elements by their position number. So you say "I want element 3" and the array goes straight to that element and gives it to you.

In a linked list, an element's position is determined only in relation to the elements before and after it. So you would usually say something like "I want the next element" and you get it quickly without having to keep track of array indices. Some languages support an array-like call to a linked list ("I want the third element of the linked list."), but it's slower than using a real array because instead of just immediately grabbing the third element, you have to get the first one, use that to find the second one, and then use that to find the third one.

Summary: Use arrays if you need fast random accesses ("Give me the 7th element"). Use linked lists if you want to think in terms of "next" and "previous" and don't need to identify elements by their position relative to the whole.