Definition of List and Linked List

List is a generic term for a collection of objects. It may or may not contain duplicates and application may or may not require that it be kept in specified order.

The functions defined to operate on a list are

·         Insert:  Insert a new entry into a list
·         Delete: Delete an entry from list
·         Length: Compute length of a list
·         Next: Return the next element in a list
·         Search: Search if an element is in a list

Linear list: A linear list is a sequence of n>=0 nodes x[1], x[2], x[3] ……………x[n] whose essential structural properties between items as they appear in a line.

Restricted list: In restricted list, Data can only be added or deleted at the ends of a structure and processing is restricted to operations at the end of lists.

The two restricted list structures are First In First Out (FIFO) stacks and Last In First Out (LIFO) queue.

The four operations performed on linear lists are

         i.            Insertion
       ii.            Deletion
      iii.            Retrieval
     iv.            Traversal

         Depending on the type of linear list, an insertion can be made at the beginning of the list, or at the end of the lists. When inserting data into ordered list, the data must be inserted so that the ordering is maintained. Deletion from general lists requires that the list be searched for the data to be deleted.

List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the lists.

List traversal is a special case of retrieval in which all the elements are retrieved in a sequence.

Definition of Linked list

A link list is a collection of records, called nodes, each containing at least one field(member) that gives the location of the next node contains two members; a data member (the value of the list item) and a link member (a value locating the next node).The link list is a very flexible dynamic data structure. It is a low-level structure upon which high-level data structures can be built.

The Typical basic linked-list operations are

         i.            Create: Makes a new linked list
       ii.            Insert: Puts a new node in its place in the list.
      iii.            Remove: Remove a node from the list.
     iv.            Traverse: This function allow user to visit each node in the list.
       v.            Is empty: The function returns a true/false indication of whether or not there are any nodes in the list.
     vi.            Is full: This function returns a true/false indication of whether or not the list is full

Types of linked lists

         i.            Singly linked lists
       ii.            Circular singly linked lists
      iii.            Doubly linked lists
     iv.            Circular Doubly linked lists

You Might also view the following Related Posts

• Fundamental of data structures
• Definition of Stack
• Definition of Queues
• Tree
• Graph Definition

For more other Posts: Click Here