LIST ADT • The list can be defined as an abstract data type in which the elements are stored in an ordered manner for easier and efficient retrieval of the elements. • The list can be called Dynamic size arrays, which means their size increased as we go on adding data in them and we need not to pre-define a static size for the list.
Various operations on the List Data Structure: • The various operations that are performed on a List Data Structure or Sequence are: • Add or Insert Operation: In the Add or Insert operation, a new item (of any data type) is added in the List Data Structure or Sequence object. • Replace or reassign Operation: In the Replace or reassign operation, the already existing value in the List object is changed or modified. • Delete or remove Operation: In the Delete or remove operation, the already present element is deleted or removed from the Dictionary or associative array object. • Find or Lookup or Search Operation: In the Find or Lookup operation, the element stored in that List Data Structure or Sequence object is fetched.
Linked list implementation • Linked List can be defined as collection of objects called nodes that are randomly stored in the memory. • A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory. • The last node of the list contains pointer to the null.
Doubly linked list • Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. • Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node.
• In C, structure of a node in doubly linked list can be given as : struct node { struct node *prev; int data; struct node *next; } • The prev part of the first node and the next part of the last node will always contain null indicating end in each direction.
Uses of Linked List • The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space. • list size is limited to the memory size and doesn't need to be declared in advance. • Empty node can not be present in the linked list. • We can store values of primitive types or objects in the singly linked list.
Applications Some important applications of a linked list include : • Allocation of Memory • Email applications • Reducing file sizes on disk • Implementation of advanced data structures

ALGORITHM ANALYSIS AND LISTS ABSTACTS DT

  • 1.
    LIST ADT • Thelist can be defined as an abstract data type in which the elements are stored in an ordered manner for easier and efficient retrieval of the elements. • The list can be called Dynamic size arrays, which means their size increased as we go on adding data in them and we need not to pre-define a static size for the list.
  • 2.
    Various operations onthe List Data Structure: • The various operations that are performed on a List Data Structure or Sequence are: • Add or Insert Operation: In the Add or Insert operation, a new item (of any data type) is added in the List Data Structure or Sequence object. • Replace or reassign Operation: In the Replace or reassign operation, the already existing value in the List object is changed or modified. • Delete or remove Operation: In the Delete or remove operation, the already present element is deleted or removed from the Dictionary or associative array object. • Find or Lookup or Search Operation: In the Find or Lookup operation, the element stored in that List Data Structure or Sequence object is fetched.
  • 3.
    Linked list implementation •Linked List can be defined as collection of objects called nodes that are randomly stored in the memory. • A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory. • The last node of the list contains pointer to the null.
  • 5.
    Doubly linked list •Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. • Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node.
  • 6.
    • In C,structure of a node in doubly linked list can be given as : struct node { struct node *prev; int data; struct node *next; } • The prev part of the first node and the next part of the last node will always contain null indicating end in each direction.
  • 7.
    Uses of LinkedList • The list is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space. • list size is limited to the memory size and doesn't need to be declared in advance. • Empty node can not be present in the linked list. • We can store values of primitive types or objects in the singly linked list.
  • 8.
    Applications Some important applicationsof a linked list include : • Allocation of Memory • Email applications • Reducing file sizes on disk • Implementation of advanced data structures