Tuesday, 17 June 2014

Linked list

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists (the abstract data type), stacksqueuesassociative arrays, and S-expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.
The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.
On the other hand, simple linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list (assuming that the last node is not maintained as separate node reference in the list structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require scanning most or all of the list elements. The advantages and disadvantages of using linked lists are as follows:-
  • Linked lists are a dynamic data structure, allocating the needed memory when the program is initiated.
  • Insertion and deletion node operations are easily implemented in a linked list.
  • Linear data structures such as stacks and queues are easily executed with a linked list.
  • They can reduce access time and may expand in real time without memory overhead.
  • They have a tendency to waste memory due to pointers requiring extra storage space.
  • Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
  • Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
  • Difficulties arise in linked lists when it comes to reverse traversing. Singly linked lists are extremely difficult to navigate backwards, and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer

Singly linked list

Singly linked lists contain nodes which have a data field as well as a next field, which points to the next
 node in line of nodes.

A singly linked list whose nodes contain two fields: an integer value and a link to the next node

Doubly linked list

In a doubly linked list, each node contains, besides the next-node link, a second link field pointing to
the previous node in the sequence. The two links may be called forward(s) and backwards, or next
and prev(previous).

A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link 
backward to the previous node
A technique known as XOR-linking allows a doubly linked list to be implemented using a single link field
in each node. However, this technique requires the ability to do bit operations on addresses, and
therefore may not be available in some high-level languages.

Multiply linked list

In a multiply linked list, each node contains two or more link fields, each field being used to connect
the same set of data records in a different order (e.g., by name, by department, by date of birth, etc.).
While doubly linked lists can be seen as special cases of multiply linked list, the fact that the two orders
are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a
separate case.

Circular list]

In the last node of a list, the link field often contains a null reference, a special value used to indicate the
lack of further nodes. A less common convention is to make it point to the first node of the list; in that
case the list is said to be 'circular' or 'circularly linked'; otherwise it is said to be 'open' or 'linear'.

                      A circular linked list
In the case of a circular doubly linked list, the only change that occurs is that the end, or "tail", of the said
list is linked back to the front, or "head", of the list and vice versa.

FOR SOME LINKED LIST PROBLEMS  YOU MAY GO HERE : http://cslibrary.stanford.edu/105/

No comments:

Post a Comment