Ask Experts » Computers » Software »

What is linked list in Data structures?

Date: 18 Apr 2011   Group: Computers    Category: Software   


Explain me in detail about linked list.


Find Answers

Author: Sandeep.M    02 May 2011      Member Level: Bronze     Points : 8  (Rs 7)    Voting Score: 0

Hi Sam,
Linked list is the most basic form of a data structure. A linked list is more or less similar to an array in that it can hold a list of values. But the similarity ceases here. The major difference between a linked list and array is that an array can hold values belonging to the same data type only whereas there is no such restriction on a linked list. For example, if an array is declared with type as int in C language, it can hold only integer values. Coming to a linked list, as it is a data structure, there is seldom any type associated with it.
Apart from the above difference, there is one more difference that makes linked lists more versatile. It is not only possible to create linear linked lists but also circular linked lists i.e., the last element of the list can be made to point to the first. Another difference is that the memory to be allocated to a linked list can be specified dynamically i.e., we need not mention the number of elements in the linked list at the time of compilation. This facility may also be available for arrays in some languages but is not widely used.
The most basic form of a linked list is created by creating a structure with one data element and a pointer to point to the next element in the data structure. The pointer of the last element is intialised to null to avoid it to point to some junk value if its a linear linked list. On the contrary, if it is a circular linked list, the pointer of the last element is made to point to the first element in the list.
The above type of list allows traversing in only one direction. If we want bi-directional traversal, then we can create a structure with two pointers where one pointer is made to point to the previous element and the other point to the next element in the list. Modifications are made as stated above for a simple linked list to convert this to a circular list. Accordingly the above two types of lists are sometimes called single linked list and double linked list.
Instead of using a single data element, we can use any number of data elements with several different data types within the structure. We may also use arrays as data elements of the linked list. An element in a linked list is often called a node. It is possible to add/delete nodes from any position within the linked list. According to the operation selected, the pointers need to be updated appropriately.
Giving a C program to create a linked list would make this response too big as the programs to create linked lists often run more than hundred lines. Nevertheless, they are simple and can be easily understood once the concept is known. For further information and programs, you can refer to standard text books like Data structures using C by A.S.Tanenbaum, Y.Langsam and M.J.Augenstein.

Author: Jayanta Datta Choudhury    03 May 2011      Member Level: Gold     Points : 3  (Rs 1)    Voting Score: 0

Hi,

The link list in computer data structure program consists of sequence of data records with reference data field in each record in order to link each data record to the subsequent data field.
The link list grows when data is added and shrinks when data is deleted in the list. Hence link list is known as dynamic data structure in conjunction with dynamic memory management techniques.
Link list in data structure have flexibility in adding, deleting or rearranging data at run time permitting additional memory space and releasing unused memory space in order to optimum use of storage space.




Author: Amruta    12 May 2011      Member Level: Bronze     Points : 5  (Rs 5)    Voting Score: 0

Linked List is a complex dynamic data structure which contains of nodes having two parts data and next.
Next is just a pointer pointing to the next node in the list. If the list is empty next just point ot NULL.
There are different types of linked list namely Singly, Doubly and Circular.
Singly Linked List is the list which can be traversed in one direction only and whose last last node of the list points to NULL.
Doubly Linked list has two pointers PREV and NEXT.This list can be traversed in both the directions. PREV of the first node of doubly linked list always points to NULL and also the NEXT of last node points to NULL.
Circular Linked List is the one whose last node points to the first instead of to the NULL.

The different operations that can be performed on list are.
INSERT:- We can dynamically insert any node at any desired position into the list.
DELETE:- Similar to insertion, deletion can also be accomplished dynamically.
TRAVERSE:- Traversing is just trvelling through the list visiting each node.

As each thing has pros and cons, the only drawback of linked list is randomly accessing of element which can be achieved through array index in array but not in linked list.The good thing about linked list is its run­time expand­abil­ity which proves its flexibility.

Author: Kothari    13 May 2011      Member Level: Gold     Points : 4    Voting Score: 0

Linked List is a Data storage mechanism in which list of data is stored in linear order. Linked list contains collection of nodes, each node contains data part and address part in which the next node address is stored.

Each node in link list contains address of next node except the last node because last node contains the NULL pointer which indicates the end of list.

Linked list has following types:

1. Singly Link List
2. Doubly Link List
3. Circular Link List

Link list data structure is created using the Structure of C as given below:

struct list
{
int data;
struct list *next;
};


The dynamic node is created using malloc() and calloc() functions available in C language and new operator is used in case of C++.

The following Operation can be performed on link list:

1.Insert element
2.Delete Element
3.Find Sum of All elements
4.Count number of node in list
5.Search any element
6.Reverse the list
7.Make copy of list
8.Merger two list
9.Update element

Link list is widely used by various real life applications.

Author: Kothari    13 May 2011      Member Level: Gold     Points : 0    Voting Score: 0

Linked list can be implemented in various applications such as Relational Database System and many other field.
Author: Mahaveer Singh    18 May 2011      Member Level: Silver     Points : 6  (Rs 5)    Voting Score: 0

Dear SAM
Linked List is basically a linear list of Elements which are linked to one another with some means of links, and hence it is known as linked list.

Each element in the list is known as Node.
And each node in the have at least two parts:-
1. Data Part
2. Link part

Data Part:- This part of every node of the list contains the information stored in that node of the list

Link Part:- This part of the node contains the memory address of the next node in the linked list.

For Example:Implementation of linked list node in C Language

Struct Node
{
int RollNo;//Data Part
int Marks;//Data Part
struct Node *link;//Address of the next Node
};

Note that the linked list contains a special node called the START which contains the address of the first node in the linked list.

if START == NULL
then it means that the linked list is Empty.

the last node of the list contains NULL in its link part which marks the end of the list.

Author: Harpreet Singh Saggu    21 Jun 2011      Member Level: Silver     Points : 3    Voting Score: 0

Linked List is a structure in data structures having a number of nodes that stores information as well as the pointer field that points to the next record to be processed. The pointer is basically a address that is used to access the next information part within a linked list. The last pointer field is filled using NULL character means there is no way further. So, it indicates the end of the linked list. Various algorithms are there to insert or delete nodes in a linked list.
It may be:

Insert element at the starting of linked list,
Insert element at the end of linked list,
Insert element at the middle of linked list,
Delete element at the starting of linked list,
Delete element at the end of linked list,
Delete element at the middle of linked list,

Author: arsha    21 Jun 2011      Member Level: Silver     Points : 5    Voting Score: 0

linked list a data structure which stores data in the form of nodes.It does not require linear memory as arrays. Each node contains a data part and a pointer part(a pointer to the next data in the list)

link or node is object of a class.there are so many types of linked list 1) single linked list
2)doubly linked list
3)circular linked list.

single linked list:
here links contains pointer to first data and last data in the list.As said earlier a pointer to the next data.
example of a linked list:

class node{// all nodes will be the objects of this class
public int data;
public link next_node;//a pointer to next data
}
public node(int data){
this.data=data;
}//end of constructor
public void showdata(){
System.out.println("data= "+data);
}
}//end of class node

After defining class for each node we need to define a class for link list. Link list contains a pointer to the first node in the list,Which should be initialized to null in the beginning. All the operations to be performed on the link list is defined as functions in this class. For example insert first,Delete,insert search etc.

class linkedlist{
private node first_node;//pointer to the first node is defined
public linkedlist(){
first_node=null;
}
public void add_DAta(int data1){
//create newnode in the memory and store data
node newnode= new node(data1);
//initially first data is null
//set the current first as the next node of the new node
newnode.next_node=first;
//set newnode as the first node
first_node=newnode;
}
}//end of class


Doubly link list:
This allows us to traverse backward and forward through the list . Here this a pointer to previous node i.e the class node in our example will have one more pointer to the previous node.
There is pointer to the last node in the list i.e class linkedlist contains pointer to last node in the list.
Circular linklist:
As the name indicate we can traversethe list i circular fashion that from first node to last node and back to firat node in the same direction. Last node will have a pointer to first node.

Answers      





Post answer or solution to "What is linked list in Data structures?"

You can earn revenue online from Google AdSense and our revenue sharing programs by post valid, self written answers for the problem What is linked list in Data structures?




You must Sign In to post a response.


Next Question: What is meant by memory mapped I/O?
Previous Question: Which is the best software for anonymous torrent download ?
Return to Question Index
Ask Question to Expert
Category: Software

 
Related Questions
Popular Tags   What are tags ?   Search Tags  

Awards & Gifts
Active Members
TodayLast 7 Daysmore...

ISC Technologies, Kochi - India. Copyright © All Rights Reserved.