Data Structures Unit - II

Linked Lists
Data processing normally involves storing and processing data organized into lists. One way to do this is arrays
but it has disadvantages in storage place in inserting and deleting an element. So, another way called linked lists is used
to store the elements. In this each element contains a field contain a link which contains the address of the next element
in the list. Thus, the successive elements in the list need not occupy adjacent memory space. So, insertion and deletion
become easy.
A linked list is a collection of data items called as Nodes/ Links. Each node is divided into two parts. The first part
contains the information and the second part contains address of the next node.
In simple words, a Linked list is a linear data structure where every element knows where the next element is present.
The structure of a node

info. address Where information holds the information associated with the node and
address hold the address of the next node in the List
In order to design a node a special type of class is used often called as Self-referential class i.e., A class having a variable
of same class type.
class Link
{
------
------ //Data
------
Link next;
}
A Linked List can be represented as,

5000 5000 7000 2000 6000

A 7000 B 2000 C 6000 D null

In order to access the linked list always the first link is address is stored. The last element address field always holds null
representing end of the linked list
Types of linked lists:
There are four types of linked lists. They are
1. Single linked list
2. Single circular linked list
3. Double linked list
4. Double circular linked list
Single Linked List:
In single linked list every element knows where the next element is present and the last node always holds null
representing the end of the list.

5000
5000 7000 2000 6000

A 7000 B 2000 C 6000 D null

In the case of single linked lists each node contains the address of only one node in the list. So, it is called as single
linked lists.

Department of Computer Science, SSBN Degree College, ATP 1

 Data Structures Unit - II

Single Circular Linked Lists:

In Circular linked lists every element holds the address of next element and the last element holds the address of
the first element forming a circular reference.

5000 5000 7000 2000 6000

A 7000 B 2000 C 6000 D 5000

The circular linked list is linked circularly i.e., up on reaching the last element the list move to first element instead of
denoting end of the list.
Double Linked Lists:
In these linked lists every element knows where the next element is present as well as where the previous element
is present i.e., storing the address of the next node as the address of previous node.
In order to achieve this the node is altered such that it holds the address next node and previous node.
Node in a double linked list

Previous Info. next

Where info. holds the information associated with the node and previous and next holds the address of the previous node
and next nodes in the list.
A double linked list is similar to single linked list. But here, each node in the list contains two address fields called
as previous and next. The previous field contains the address of the previous node and the next field contains the address
of the next node. Since every link in the list maintains the address of two nodes, list is called as the double linked list. The
first link previous field and last link next field hold null representing the beginning of the list and end of the list.

7000

7000 2000 5000

null A 2000 7000 B 5000 2000 C null

Double Circular Linked Lists:

It is similar to double linked list except the last node holds the address of the first node and the first node holds
the address of the last node forming two circular references i.e., the previous field of first node contains the address of
the last node and the next field of the last node contains the address of the first node. So, it is called as double circular
linked list.

7000

7000 2000 5000

5000 A 2000 7000 B 5000 2000 C 7000

Double liked lists are also called as two-way list. In these lists it is possible to traverse the list in two directions i.e., the
forward direction from the beginning of the list to the end and the backward direction from the end of the list to the be

Department of Computer Science, SSBN Degree College, ATP 2

 Data Structures Unit - II

Memory Allocation:
The maintenance of linked list in memory assumes the possibility of inserting new nodes into the lists and hence
it requires a method, which provides unused memory space for the new nodes, and other way whereby the memory space
of deleted nodes becomes available for future use. In memory, with linked list, a special list is maintained which consists
of unused memory cells called the list of available space or free pool.
Garbage Collection:
When a node is deleted from a list the memory space becomes reusable. This can be done by immediately
reinserting the space into the free storage, but this is time consuming for the operating system, so the operating system
periodically collects all the deleted space on to the free-storage list. The technique, which uses this collection, is called
garbage collection. This takes place when there is only some minimum amount of space is available. First the computer
runs through all lists, tagging those cells, which are currently in use, and then it runs through the memory collecting all
untagged space onto the free-storage list.
Overflow and Underflow:
When inserting an element into the data structure if the space is not available i.e., the free storage list is empty.
This situation is called overflow. Similarly, the underflow refers to the situation where one wants to delete data from an
empty list.
Single Linked Lists:
In order to create single linked list, we need to create individual links first with the help of class and in order to
maintain all the links in the list a separate class is used called as Linked list.
The Link Class
class Link
{
public int rollNo;
public String name;
public Link next;
public Link (int rNo, String n)
{
rollNo=rNo;
name=n;
}
public void displayLink ()
{
System.out.print("{"+rollNo+","+name+"}");
}
}
Here the rollNo and name are the information associated with the node and next is the referential variable to hold the
address of the next node in the list.

The LinkList Class

The LinkList class contains only one element called as first which is used to maintain the address of first link in the
list. Since in order to process the list, it’s mandatory to know the starting address of the list. Using the first link address all
the Links can be processed very easily.
Basic operations on Single Linked lists
• Inserting an item at the beginning of the list.
• Deleting the item at the beginning of the list.
• Display the contents of the entire list.
Advanced operations of Single Linked lists
• Search for a given element in the list.
• Delete a specified element form the list.

Department of Computer Science, SSBN Degree College, ATP 3

 Data Structures Unit - II

Link List as ADT:

class LinkList
{
private Link first;
public void LinkList( )
{
first = null;
}
public boolean isEmpty ()
{
return(first==null);
}
public void insertFirst (----)
{
======
}
public Link deleteFirst ()
{
=====
}
public void displayList ()
{
======
}
}
Here LinkList () constructor initializes the List by assigning null to first, since when the list is created it is empty.
The isEmpty () method returns true only when the list is empty otherwise false is returned
insertFirst () methods inserts an element at the beginning of the list
deleteFirst () methods deletes an element from the beginning of the list and displayList displays the entire linked list

Inserting an element at the beginning of the List:

The insertFirst () method of LinkList inserts a new link at the beginning of the list. This is the easiest place to insert
a link because first already points to the first link. To insert the new link, we need only set the next field in the newly
created link to point to the old first link and then change first so it points to the newly created link.
Procedure for inserting an element at beginning of the List is as follows
• Create a Link with specified values.
• Now store the address of first link in newly created Link’s address field.
• Lastly store the address of newly created Link in first variable.

Method:
public void insertFirst (int rNo, String n)
{
Link L=new Link (rNo, n);
L.next=first;
first=L;
}

Department of Computer Science, SSBN Degree College, ATP 4

 Data Structures Unit - II

Deleting an element at the beginning of the List:

The deleteFirst () method is the reverse of insertFirst (). It disconnects the first link by rerouting first to point to
the second link. This second link is found by looking at the next field in the first link.
Procedure for deleting an element from the beginning of the List is as follows
• Create a temporary Link and assign first link address in it.
• Now remove the Link by simply storing the second link address in first variable as., first = first.next;
• Lastly return the deleted Link.

Method:
public Link deleteFirst ()
{
Link temp=first;
first=first.next;
return temp;
}
Displaying the list:
Displaying the list is similar to traversing of the list from first element to the last element. This can be achieved by
using a reference which is moved from first link to last link and in each time the corresponding link is displayed.
Procedure for displaying the entire list is as follows
• Create a temporary Link (say current) and assign first link address in it.
• Now display the link using displayLink () method of Link class.
• Advance to next link by changing the address of temporary link to next link in the list (current = current.next;)
• Repeat this process until the of temporary link attains null since it represents the end of the list.

Method:
public void displayList ()
{
System.out.print(“List [: “);
Link current = first;
while (current! =null)
{
current. displayLink ();
current = current.next;
}
System.out.println(“] “);
}

Department of Computer Science, SSBN Degree College, ATP 5

 Data Structures Unit - II

//Program demonstrates linked list

class Link
{
public int rollNo;
public String name;
public Link next;
public Link (int rNo, String n)
{
rollNo=rNo;
name=n;
}
public void displayLink ()
{
System.out.print("{"+rollNo+","+name+"}");
}
}
class LinkList
{
public Link first;
public LinkList ()
{
first=null;
}
public boolean isEmpty ()
{
return (first==null);
}
public void insertFirst (int rNo, String n)
{
Link L=new Link(rNo, n);
L.next=first;
first=L;
}
public Link deleteFirst()
{ Output
Link temp=first; List:[{17004,Teja}{17003,Hari}
first=first.next; {17002,Divya}{17001,Raju}]
return temp; Deleted Link :
} {17004,Teja}
public void displayList() List:[{17003,Hari}{17002,Divya}{1700
{ 1,Raju}]
System.out.print("\nList:[");
Link current=first;
while(current!=null)
{
current.displayLink();
current=current.next;
}
System.out.println("]");
}
}
public class LinkListApp
{
public static void main(String[] args)
{
LinkList LST=new LinkList();
LST.insertFirst(17001, "Raju");
LST.insertFirst(17002, "Divya");
LST.insertFirst(17003, "Hari");
LST.insertFirst(17004, "Teja");
LST.displayList();
Link temp=LST.deleteFirst();
System.out.println("Deleted Link :");
temp.displayLink();
LST.displayList();

Department of Computer Science, SSBN Degree College, ATP 6

 Data Structures Unit - II

Finding specified Link in the list:

In order to find specified the link in list, the list has to traverse from first element last element. When the search
element is found then the search is stopped and Link is returned otherwise null is returned representing element is not
present in the list.
Procedure for displaying the entire list is as follows
• Create a temporary link (say current) and assign the address of first link of the list.
• Check whether the temporary is the element to be found if so, search is stopped and link is returned.
• If not advance to next link by changing the address of temporary link to next link in the list ( current = current.next;)
• This process is continued till element is found or the list ends. If still the element is not found then null is returned

Method:
public Link find(int key)
{
Link current=first;
while(current!=null)
{
if(current.rollNo==key)
return current;
current=current.next;
}
return null;
}

Delete a specified element form the list:

The delete( ) Method
In order to delete specific item from the list, the element to be deleted and its previous element should be found.
Because once both the elements are found then by simply placing the next element address in the previous link removes
the element
Procedure delete specific item from the list is as follows
• Create two temporary links (say current and previous) and assign the address of first link of the list.
• Check whether the temporary is the element to be found if so, search is stopped.
• If not advance such that the two links always refer two consecutive links in the list.
( previous =current and current = current.next;)
• This process is continued till element is found or the list ends. If still the element is not found then null is returned
• After finding the element if it is first element then it can be deleted as first = first.next;
• If not then it can be deleted as previous.next = current.next;

Department of Computer Science, SSBN Degree College, ATP 7

 Data Structures Unit - II

Method:
public Link delete(int key)
{
Link current,previous;
current=previous=first;
while(current.rollNo!=key)
{
if(current.next==first)
return null;
previous=current;
current=current.next;
}
if(current==first)
first=first=first.next;
else
previous.next=current.next;
return current;
}
//Program to illustrate find a specific link and delete a specific link in the linked list
class Link
{
public int rollNo;
public String name;
public Link next;
public Link(int rNo,String n)
{
rollNo=rNo;
name=n;
}
public void displayLink()
{
System.out.print("{"+rollNo+","+name+"}");
}
}
class LinkList
{
public Link first;
public LinkList()
{
first=null;
}
public boolean isEmpty()
{
return (first==null);
}
public void insertFirst(int rNo,String n)
{
Link L=new Link(rNo,n);
L.next=first;
first=L;
}
public Link deleteFirst()
{
Link temp=first;
first=first.next;
return temp;
}

Department of Computer Science, SSBN Degree College, ATP 8

 Data Structures Unit - II
public Link find(int key)
{
Link current=first;
while(current!=null)
{
if(current.rollNo==key)
return current;
current=current.next;
}
return null;
}
public Link delete(int key)
{
Link current,previous;
current=previous=first;
while(current.rollNo!=key)
{
if(current.next==first)
return null;
previous=current;
current=current.next;
}

if(current==first)
first=first=first.next;
else
previous.next=current.next;
return current;
}
public void displayList()
{
System.out.print("\nList:[");
Link current=first;
while(current!=null)
{
current.displayLink();
current=current.next;
}
System.out.println("]");
}
}
public class LinkSearchApp
{
public static void main(String[] args)
{
LinkList LST=new LinkList();
LST.insertFirst(17001, "Raju");
LST.insertFirst(17002, "Divya");
LST.insertFirst(17003, "Hari");
LST.displayList();
Link temp=LST.find(17003);
if(temp!=null)
System.out.println("Found Link with key: "+temp.rollNo);
else
System.out.println("Link not found");
temp=LST.delete(17002);
if(temp!=null)
System.out.println("DeletedLinkwith key: "+temp.rollNo);
else
System.out.println("Link not found");
LST.displayList()
}
}

Department of Computer Science, SSBN Degree College, ATP 9

 Data Structures Unit - II

Double-Ended Lists
A double-ended list is similar to an ordinary linked list, but it has one additional feature a reference to the last link
as well as to the first. The reference to the last link enables to insert a new link directly at the end of the list as well as at
the beginning. Of course, you can insert a new link at the end of an ordinary single-ended list by iterating through the
entire list until you reach the end, but this approach is inefficient.
Access to the end of the list as well as the beginning makes the double-ended list suitable for certain situations
that a single-ended list can’t handle efficiently. The double ended list can be used to simulate First-in-fist-out data
structures like Queues where the insertions and deletions must be in at two different ends.
Basic operations performed on Double ended lists:
• Inserting an element at the beginning of the list.
• Inserting an element at the end of the list.
• Deleting an element at the beginning of the list.
Double ended list as ADT:
class DoubleEndedList
{
private Link first, last;
public DoubleEndedList ( )
{
first=last = null;
}
public boolean isEmpty( )
{
return(first==null);
}
public void insertFirst( ----)
{
======
}
public void insertLast( ----)
{
======
}

public Link deleteFirst()

{
=====
}
public void displayList()
{
======
}
}
Inserting an element at the beginning of the List:
The insertFirst( ) method of Double Ended List inserts a new link at the beginning of the list. This is the easiest
place to insert a link because first already points to the first link. To insert the new link, we need only set the next field in
the newly created link to point to the old first link and then change first so it points to the newly created link. But if the
list is empty and a new link is adding to the list then the last must store the address of newly created link.
Procedure for inserting an element at beginning of the Double Ended list is as follows
• Create a Link with specified values.
• Check whether the list is empty or not if so store the address of new link in last variable.
• Now store the address of first link in newly created Link’s address field.
• Lastly store the address of newly created Link in first variable.

Department of Computer Science, SSBN Degree College, ATP 10

 Data Structures Unit - II

Method:
public void insertFirst(long d)
{
Link L = new Link(d);
if(isEmpty())
last = L;
L.next = first;
first = L;
}
Inserting an element at the last of the List:
The insertLast( ) method of Double Ended List inserts a new link at the end of the list. To insert the new link, we
need only set the next field of last link to point newly created link. Change last variable so it points to the newly created
link. But if the list is empty and a new link is adding to the list then the first must store the address of newly created link.
Procedure for inserting an element at end of the Double Ended list is as follows
• Create a Link with specified values.
• Check whether the list is empty or not if so store the address of new link in last variable.
• If the list is not empty then store the address new link in last link.
• Lastly store the address of newly created Link in last variable.

/////////

Method:
public void insertLast(long d)
{
Link L = new Link(d);
if(isEmpty())
first = L;
else
last.next = L;
last = L;
}

Department of Computer Science, SSBN Degree College, ATP 11

 Data Structures Unit - II

Deleting an element at the beginning of the List:

The deleteFirst( ) method is the reverse of insertFirst( ). It disconnects the first link by rerouting first to point to
the second link. This second link is found by looking at the next field in the first link.
Procedure for deleting an element from the beginning of the List is as follows
• Create a temporary Link and assign first link address in it.
• Check whether the list contains only one element is so then initial conditions are applied (i.e., first = last = null).
• Otherwise remove the Link by simply storing the second link address in first variable as ., first = first.next;
• Lastly return the deleted Link.

///

Method:
public Link deleteFirst()
{
Link temp = first;
if(first.next == null)
last = null;
first = first.next;
return temp;
}
//Program to illustrate Double Ended List
class Link
{
public long data;
public Link next;
public Link(long d)
{
data = d;
}
public void displayLink()
{
System.out.print(data +" ");
}
}
class DoubleEndedList
{
private Link first, last;
public DoubleEndedList ()
{
first =last = null;
}
public boolean isEmpty()
{
return first==null;
}
public void insertFirst(long d)
{
Link L = new Link(dd);
if(isEmpty())
last = L;
L.next = first;
first = L;
}

Department of Computer Science, SSBN Degree College, ATP 12

 Data Structures Unit - II
public Link deleteFirst()
{
Link temp = first;
if(first.next == null)
last = null;
first = first.next;
return temp;
}
public void insertLast(long d)
{
Link L = new Link(d);
if(isEmpty())
first = L;
else
last.next = L;
last = L;
}

public void displayList()

{
System.out.print("List :[ ");
Link current = first;
while (current !=null)
{
current.displayLink();
current = current.next;
}
System.out.println("]");
}
}
class DoubleEndedListApp
{
public static void main(String[] args)
{
DoubleEndedList DList;
DList = new DoubleEndedList ();
DList.insertFirst(22);
DList.insertFirst(44);
DList.insertFirst(66);
DList.insertLast(11);
DList.insertLast(33);
DList.insertLast(55);
DList.displayList();
DList.deleteFirst();
DList.deleteFirst();
DList.displayList();
}
}

Output:
List (first -->last): 66 44 22 11 33 55
List (first -->last): 22 11 33 55

Department of Computer Science, SSBN Degree College, ATP 13

 Data Structures Unit - II

Linked-List Efficiency
The Insertion and deletion at the beginning of a linked list are very fast. They involve changing only one or two
references, so the time taken for those operations will be constant i.e., takes O (1) time.
Finding, deleting or inserting next to a specific item requires searching through the list, on the average, half the
items in the list. This requires O (N) comparisons. An array is also takes O (N) time for these operations, but the linked list
is nevertheless faster because nothing needs to be moved when an item is inserted or deleted. The increased efficiency
can be significant, especially if a copy takes much longer than a comparison.
Of course, another important advantage of linked lists over arrays is that a linked list uses exactly as much memory
as it needs and can expand to fill all of available memory. The size of an array is fixed when it’s created; this usually leads
to inefficiency because the array is too large, or to running out of room because the array is too small. Vectors, which are
expandable arrays, may solve this problem to some extent, but they usually expand in fixed-sized increments (such as
doubling the size of the array whenever it’s about to overflow). This solution is still not as efficient a use of memory as a
linked list.
Abstract Data Types
An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the data and the
operations that are allowed without regard to how they will be implemented. This means that we are concerned only with
what the data is representing and not with how it will eventually be constructed. By providing this level of abstraction, we
are creating an encapsulation around the data. The idea is that by encapsulating the details of the implementation, we
are hiding them from the user’s view. This is called information hiding.
In simple words, it’s a way of looking at a data structure: focusing on what it does and ignoring how it does its job.
Stacks and queues are examples of ADTs.
Stack Implemented by a Linked List:
A stack can easily implemented using a Single Linked List. Since in a stack elements are to inserted and deleted at
only one end. The primitive operations of the stack like push and pop are implemented using insertFirst() and deleteFirst()
operations of the Linked List.
Representing Stacks as ADT using Linked Lists
class Link
{
public int rollNo;
public String name;
public Link next;
public Link(int rNo,String n)
{
rollNo=rNo;
name=n;
}
public void displayLink()
{
System.out.print("{"+rollNo+","+name+"}");
}
}
class StackLinkList
{
public Link top;
public StackLinkList()
{
top=null;
}
public boolean isEmpty()
{
return (top==null);
}

Department of Computer Science, SSBN Degree College, ATP 14

 Data Structures Unit - II
public void push(int rNo,String n)
{
Link L=new Link(rNo,n);
L.next=top;
top=L;
}
public void pop()
{
if(isEmpty())
{
System.out.println("Stack is empty");
return;
}
Link temp=top;
top=top.next;
System.out.println("Popped element from Stack is :");
temp.displayLink();
}
public void displayStack()
{
System.out.print("Stack :[");
Link current=top;
while(current!=null)
{
current.displayLink();
current=current.next;
}
System.out.println("]");
}
}
public class LinkStackApp
{
public static void main(String[] args)
{
LinkStack STK=new LinkStack();
STK.push(17001, "Raju");
STK.push(17002, "Divya");
STK.push(17003, "Hari");
STK.push(17004, "Teja");
STK.displayStack();
STK.pop();
STK.pop();
STK.displayStack();
}
}

Output:
Stack:[{17004,Teja}{17003,Hari}{17002,Divya} {17001,Raju}]
Stack:[{17002,Divya}{17001,Raju}]

Department of Computer Science, SSBN Degree College, ATP 15

 Data Structures Unit - II

Queue Implemented by a Linked List:

A Queue cannot be implemented using a single linked list because in a queue the elements have to be inserted
at one end and they are supposed to delete from another end. To enable this a double ended list is used to implement
queue data structure. The primitive operations of queue like insert and delete are performed with insertLast() and
deleteFirst() operations of double ended list.
Representing Queue as ADT using Linked Lists
class Link
{
public long data;
public Link next;
public Link(long d)
{
data=d;
}
public void displayLink()
{
System.out.print(data+" ");
}
}

class QueueLinkList
{
public Link front,rear;
public QueueLinkList()
{
front=rear=null;
}
public boolean isEmpty()
{
return (front==null);
}
public void insert(long d)
{
Link L=new Link(d);
if(isEmpty())
front=rear=L;
else
rear.next=L;
rear=L;
}
public void delete()
{
if(isEmpty())
{
System.out.println("Queue is empty");
return;
}
Link temp=front;
if(front.next==null)
rear=null;
front=front.next;
System.out.println("Removed element from Queue is :");
temp.displayLink();
}
public void displayQueue()
{
Link current=front;
System.out.print("Queue:[");
while(current!=null)
{
current.displayLink();
current=current.next;
}
System.out.println("]");
}
}

Department of Computer Science, SSBN Degree College, ATP 16

 Data Structures Unit - II
public class LinkQueueApp
{
public static void main(String[] args)
{
LinkQueue Q=new LinkQueue();
Q.insert(695);
Q.insert(565);
Q.insert(275);
Q.insert(435);
Q.insert(865);
Q.insert(345);
Q.displayQueue();
Q.delete();
Q.delete();
Q.displayQueue();
}
}
Output:
Queue:[695 565 275 435 865 345 ]
Queue:[275 435 865 345 ]

Data types and Abstraction:

Data types are the built-in data types such as int, float, char, double... They are also called as Primitive Types. A
data type always specifies two things: a data item with certain characteristics and permissible operations on that data. For
example, in java when a variable is declared as int then it should contain whole non decimal number ranging from -231 to
+231-1 and the operators +, -, *, /, % can be applied on them, the permissible operations on the data types are an
inseparable part of their identity. With object-oriented programing it is possible to create own data types using classes.
For example, Stacks and Queues represented as Classes can also be treated as data types.
Abstraction:
The word abstract means “considered apart from detailed specifications or implementation.” An abstraction is
the essence or important characteristics of something. In object-oriented programming, an Abstract Data Type is a class
considered without regard to its implementation. It’s a description of the data in the class (fields), a list of operations
(methods) that can be carried out on that data, and instructions on how to use these operations. Specifically excluded are
the details of how the methods carry out their tasks. The user only knows what the methods are to call, how to call them,
and they get the results as they expect, but not how they work.
For example, stack, the user knows that push () and pop() (and perhaps a few other methods) exist and how they work.
The user doesn’t (at least not usually) need to know how push() and pop() work, or whether data is stored in an array, a
linked list, or some other data structure like a tree. An ADT specification is often called an Interface. It’s what the class
user sees—usually its public methods. In a stack class, push() and pop() and similar methods form the interface.
ADT Lists:
A list (sometimes called a linear list) is a group of items arranged in a linear order. That is, they’re lined up in a
certain way, like beads on a string or houses on a street. Lists support certain fundamental operations. That is, insert an
item, delete an item, and usually read an item from a specified location. ADT list and linked lists are different. A list is
defined by its interface: the specific methods used to interact with it. This interface can be implemented by various
structures, including arrays and linked lists. The list is an abstraction of such data structures.
ADTs as a Design Tool:
The ADT concept is a useful aid in the software design process. That is., when data is need to be stored then
consider the operations need to be performed on that data like accessing to the last item inserted or the first one, element
with a specified key, elements current position… Answering such questions leads to the definition of an ADT. Only after
the ADT is completely defined then the details of how to represent the data and how to code the methods that access the
data are defined.

Department of Computer Science, SSBN Degree College, ATP 17

 Data Structures Unit - II

By decoupling the specification of the ADT from the implementation details, it simplifies the design process and
also make it easier to change the implementation in future time.
Once the ADT has been designed, the underlying data structure must be carefully chosen to make the specified
operations as efficient as possible. For example, if an element needs to be random accessed then linked-list representation
isn’t an efficient operation instead using an array is efficient.
NOTE
Remember that the ADT concept is only a conceptual tool. Data storage structures are not divided cleanly into
some that are ADTs and some that are used to implement ADTs. A linked list, for example, doesn’t need to be wrapped in
a list interface to be useful; it can act as an ADT on its own, or it can be used to implement another data type such as a
queue. A linked list can be implemented using an array, and an array-type structure can be implemented using a linked
list. What’s an ADT and what’s a more basic structure must be determined in a given context.

Department of Computer Science, SSBN Degree College, ATP 18