Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | Array Implementation of Lists List

A list is a sequential data structure, ie. a collection of items accessible one after another beginning at the head and ending at the tail.

**ARRAY IMPLEMENTATION OF
LISTS LIST:**

A list is a sequential data structure,
ie. a collection of items accessible one after another beginning at the head
and ending at the tail.

It is a widely used data structure for
applications which do not need random access Addition and removals can be made
at any position in the list

lists are normally in the form of a_{1},a_{2},a_{3}.....an.
The size of this list is n.The first element of the list is a1,and the last
element is an.The position of element ai in a list is i.

List of size 0 is called as null list.

**Basic Operations on a List**

Creating a list

Traversing the list

Inserting an item in the list

Deleting an item from the list

Concatenating two lists into one

Implementation
of List:

A
list can be implemented in two ways

1. Array
list

2. Linked
list

**1.Storing
a list in a static data structure(Array List)**

This implementation stores the list in an array.

The
position of each element is given by an index from 0 to n-1, where n is the
number of elements.

The
element with the index can be accessed in constant time (ie) the time to access
does not depend on the size of the list.

The
time taken to add an element at the end of the list does not depend on the size
of the list. But the time taken to add an element at any other point in the
list depends on the size of the list because the subsequent elements must be
shifted to next index value.So the additions near the start of the list take
longer time than the additions near the middle or end.

Similarly
when an element is removed,subsequent elements must be shifted to the previous
index value. So removals near the start of the list take longer time than
removals near the middle or end of the list.

**Problems
with Array implementation of lists:**

Insertion
and deletion are expensive. For example, inserting at position 0 (a new first
element) requires first pushing the entire array down one spot to make room,
whereas deleting the first element requires shifting all the elements in the
list up one, so the worst case of these operations is O(n).

Even
if the array is dynamically allocated, an estimate of the maximum size of the
list is required. Usually this requires a high over-estimate, which wastes
considerable space. This could be a serious limitation, if there are many lists
of unknown size.

Simple
arrays are generally not used to implement lists. Because the running time for
insertion and deletion is so slow and the list size must be known in advance

**2.
Storing a list in a dynamic data structure(Linked List)**

The
Linked List is stored as a sequence of linked nodes which are not necessarily
adjacent in memory.

Each
node in a linked list contains data and a reference to the next node The list
can grow and shrink in size during execution of a program.

The
list can be made just as long as required.It does not waste memory space
because successive elements are connected by pointers.

The
position of each element is given by an index from 0 to n-1, where n is the
number of elements.

The
time taken to access an element with an index depends on the index because each
element of the list must be traversed until the required index is found.

The
time taken to add an element at any point in the list does not depend on the
size of the list,as no shifts are required

Additions
and deletion near the end of the list take longer than additions near the
middle or start of the list. because the list must be traversed until the
required index is found

**1. Array versus Linked Lists 1.Arrays are
suitable for**

- Randomly
accessing any element.

- Searching
the list for a particular value

- Inserting
or deleting an element at the end.

**2.Linked
lists are suitable for**

-Inserting/Deleting
an element.

-Applications
where sequential access is required.

-In
situations where the number of elements cannot be predicted beforehand.

**LINKED LIST IMPLEMENTATION OF LISTS(POINTERS)**

The Linked List is stored as a sequence of linked nodes which are not necessarily adjacent in memory.

Each node in a linked list contains data and a reference to the next node The list can grow and shrink in size during execution of a program.

In the array implementation,

1. we are constrained to use contiguous space in the memory

2. Insertion, deletion entail shifting the elements

Pointers overcome the above limitations at the cost of extra space for pointers.

data structure that will be used for the nodes. For list where each node holds a float:example, the following struct could be used to create a

struct Node

{

int node ;

struct Node *next;

};

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.