linked list

• Linked Lists in 10 minutes - I

http://www.youtube.com/watch?v=LOHBGyK3Hbs&feature=related

Disadvantages of arrays are
-when element is added all elements need to be shifted
-fixed size

with linked list these problems are overcame

• linked list in plain english

http://www.youtube.com/watch?v=oiW79L8VYXk

• advantages

The biggest advantage of linked lists is that they can be expanded in constant time without memory overhead. 

For example when you make an array you must allocate memory for a certain number of elements. 
If you want to add more elements to the array than you allocated for you must create a new array and copy the old array into the new array. 
This can take lots of time. 
You can prevent this by allocating lots of space initially but then you might allocate more than you need wasting memory. 

With a linked list you can start with space for just one element allocated. And add on new elements easily without the need to do any copying and reallocating. 

Read more: http://wiki.answers.com/Q/What_are_the_advantages_of_linked_lists#ixzz1xDOa8ksU

• Linked lists have several advantages over dynamic arrays. 

Insertion or deletion of an element at a specific point of a list, assuming that we have a pointer to the node (before the one to be removed, or before the insertion point) already, is a constant-time operation, whereas insertion in a dynamic array at random locations will require moving half of the elements on average, and all the elements in the worst case.
While one can "delete" an element from an array in constant time by somehow marking its slot as "vacant", this causes fragmentation that impedes the performance of iteration.

Moreover, arbitrarily many elements may be inserted into a linked list, limited only by the total memory available; while a dynamic array will eventually fill up its underlying array data structure and will have to reallocate — an expensive operation,


http://en.wikipedia.org/wiki/Linked_list#Linked_list_operations

• Linked lists are preferable over arrays when:

a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)

b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big

c) you don't need random access to any elements

d) you want to be able to insert items in the middle of the list (such as a priority queue)

• Arrays are preferable when:

a) you need indexed/random access to elements

b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array

c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.

d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.

Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

http://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list

• When should I use LinkedList?

When you need efficient removal in between elements or at the start.
When you don't need random access to elements, but can live with iterating over them one by one

• When should I use ArrayList?

When you need random access to elements ("get the nth. element")
When you don't need to remove elements from between others. It's possible but it's slower since the internal backing-up array needs to be reallocated.
Adding elements is amortized constant time (meaning every once in a while, you pay some performance, but overall adding is instantly done)

• Making the decision

If your data is best represented using a multidimensional structure, or the number of elements is known in advance and will remain consistent, an array is best.
If your data is easily represented in one dimension, and the number of elements is unknown or is expected to change often throughout the operation of your program, a linked list is more efficient.

If your data will be searched and accessed often but will change infrequently, the array offers the least overhead for your expected operations.
If you expect to be regularly adding or subtracting elements, especially if you need to maintain a sorted order, the versatility of the linked list will be of greater benefi

http://www.techrepublic.com/article/deciding-whether-to-use-arrays-or-linked-lists/1050183



ArrayList is very useful when a well defined set of data is needed in a List interface as opposed to an array. It can be dynamically changed, but try not to do so frequently throughout the life of the application. LinkedList is there for you to do just that: Manipulating it is very easy, and as long as its used for iteration purposes only and not for random accessing, it’s the best solution. Further, if you need random accessing from time to time, I suggest toArray for that specific moment.

http://chaoticjava.com/posts/linkedlist-vs-arraylist/

• Bagli listeler

Programlama açisindan liste, aralarinda dogrusal iliski olan veriler toplulugu olarak görülebilir. 

Yigit ve kuyruklarin genisletilmesi yani üzerlerindeki sinirlamalarin kaldirilmasi ile liste yapisina ulasilir.

Yigitlarda ve kuyruklarin gerçeklestiriminde sirali bellek kullaniminin (dizi) en büyük dezavantaji, hiç kullanilmasa veya az kullanilsa bile sabit miktardaki

bellegin bu yapilara ayrilmis olarak tutulmasidir.

Ayrica sabit bellek miktari asildiginda da tasma olusmasi ve eleman ekleme isleminin yapilamamasidir. 

Bagli listeler üzerinde gerçeklestirildiklerinde ise bu problemler ortadan kalkmaktadir.

Bir bagli listenin n. elemanina erismek için n tane islem yapmak yani kendinden önceki (n-1) eleman üzerinden geçmek gerekmektedir. 

Elemanlarin bellekteki yerleri dizilerdeki gibi sirali olmadigindan elemanlar ve siralari ile yerlestikleri bellek bölgeleri arasinda bir iliski yoktur.

Circular Linked Lists

Son elemanin bagi NULL degildir; ilk elemani gösterir.

Doubly Linked Lists

Her dügümü iki bag içerdigi bagli listelerdir.

ilk bag kendinden önceki dügümü gösterirken ikincisi de kendinden sonraki dügümü gösterir

Çift bagli listelerde, tek bagli listelerdeki geriye dogru listeleme ve dolasmadaki zorluklar ortadan kalkar.

Circular Doubly Linked Lists

ilk dügümden önceki dügüm son, son dügümden sonraki dügüm de ilk dügümdür.