Is an array a type of linked list?

Is an array a type of linked list?

Attached: 1532208418844s.jpg (250x250, 10K)

Other urls found in this thread:

youtube.com/watch?v=_jQhALI4ujg
twitter.com/NSFWRedditImage

No

What's the difference then?

array is sequential in memory

Name 3 common things between an array and a linked list besides "they store data".

Short answer: no.
Long answer: nooooooooooo.

It's a hardware-optimized linked list

>optimized linked list
>insertion isn't O(1)

Amortized back inserts are O(1) though.

Yes, the links are even helpfully calculated for you using sizeof.

elements in an array are not LINKED to each other, they're only stored in a defined space

Define array. Define linked list.

Yes

you're confunding a list interface with a potential list implementation. a list interface is a set of methods to use a list. a list implementation can use array (arraylist) or a linkedlist (same name).

a linked list allocates memory on the heap usually, with each insertion adding a new node and pointing to the next one. the arraylist prealocates memory, and usually has a fixed size. if you want to insert elements past the list size, either you can't or you need to realocate everything. arrays are usually on the stack

They're linear data structures
each element is identified by a unique index
the indexes of both are sequential

they're more similar than different, I'd say that linked lists and arrays are just different implementations of a 'list'.

Arrays are contiguous. Linked lists are not.

>indexes of linked lists are sequential
THE ABSOLUTE STATE OF Jow Forums

I don't understand when people say that linked list insertion is O(1).

Say, you want to insert a cell at position 10. First you need to walk through the 9 initial elements to even get there, change the pointer of the 9th one to a new element, then have the new element point to the rest of the list. It's O(n).

Insert it at the head you fucking tard

>indexes = addresses
Retard.

Jesus christ user

>Calling me a retard when you say lists have indexes
Lists don't have fucking indexes, you invalid bellend. They only keep track of the previous and next node of the list (depending on whether it is doubly, singly or multiply linked). Use the right fucking terminology faggot. Index has a definite meaning when we're talking about computer science and they are associated with arrays and hash tables, not fucking linked lists, you mentally challenged brainlet.

they don't even have indexes wtf

lists have indexes
implementation is never gonna change that

You can still implement an o(n) index function, you unimaginative bellend.

How do you find the index of a node in a 2-dimensional list (as in it has a previous and next node and an "upper" and "lower" node)?

*as in each node in the list has

Memory addresses are their indices

That's called an append.

By traversing it brainlet. CS 101.

So you're admitting that lists have O(n) access times because they have only sequential access meanwhile arrays and hashtables have O(1) access times because they have indexes that allow for them to access any member of that data structure without going through every single member before it? So why are you pretending to be retarded and saying lists have indexes?

Attached: HayekMisesLaughing.jpg (527x283, 84K)

Good thread.

Attached: 1527531621444.jpg (638x558, 64K)

>I'm a brainlet because I know that arrays aren't lists and linked lists don't have indexes

No it's not.
Watch and learn youtube.com/watch?v=_jQhALI4ujg

An array take out a sequential "row" in memory. That is why you can not increases it size. Linked lists differ, in that their memory does not have to be taken out in row format, it can be seperated into different chunks. This is because linked lists contain a pointer to where the next memory address is. Take for example this picture


Let - = Memory
Let X = Memory not available.

An array would look like this

XXX---------------XXXX
Where the array has taken out a "row" of memory. It can not grow any further, and its all sequential.

A linked list could look like this:
XX---XX-XXXXX--------X--X-X

This is allowed for linked list, because each node know where the next memory is. It does not have to be sequential

He's right though. Indexes are something you can jump to immediately. If you have to iterate over everything, that's not called an index, that's called brute force search. This is not a new concept, books have had indexes for a long time, flipping through each page to find a word is not called "indexing".

yes

/thread