Difference between Vector and Linked list ADT

can someone explain to me the difference between Vector and Linked List ADT 开发者_开发百科in a c programming language context.

Thanks.

---

Well, in C, there are no "vector" and "list" data types available to you directly like in C++ std library. But in terms of "abstract data type", a vector is usually considered to represent contiguous storage, and a linked list is considered to be represented by individual cells linked together. Vectors provide fast constant time random-access read and write operations, but inserting and deleting vector elements take linear time. Lists have linear lookup performance to find an element to read and write, but given an element location, have constant time insertion and deletion. You can also add items to the start and to the end of a list in constant time (if the ADT implementation caches the location of the last element in the list).

---

A vector is often implemented as a contiguous block of memory as an array. Whereas a list can be spread across memory as each element holds pointers to one or more other elements (could be doubly linked). This gives vectors the access speed advantage but lists the insertion/deletion advantage.

---

Basically, a vector resides in contiguous memory. A linked list contains pointers to the previous and next structures. Vector is faster for random access, the linked list is better for growing.

http://www.codeguru.com/forum/archive/index.php/t-309352.html

---

vector is a dynamic array. the elements inside is adjacent in the memory. The elements inside linked list is not adjacent.