Thursday, August 15, 2013
Linked List Data Structure
A linked list data structure is perhaps the simplest following an array. It consists of a set of elements wherein each element points to the next. It does not require a contiguous area of memory unlike an array. Adding to a linked list can be as simple as setting the new element as the first element of the list or finding the last item of the list and making the new item the last item. Removing an element requires searching for the previous element of the list, unless the element to be removed is the first item, in which case the removal is quite simple. Searching for an element is no simpler than an array, which requires a comparison with each of the elements. A variation of the sorted list, like a sorted array, makes searching for elements easier while adding complexity to the addition of new elements. However, addition of a new item to the middle of a linked list is much simpler than adding to the middle of an array - an array requires all subsequent elements to be shifted whereas a linked list requires the pointer of the previous element to be set to the new element and the pointer from the new element to be set to the next element. Linked lists are good for implementing stacks with addition and removal occurring from the head of the linked list.