Copyright

Practical Application for C Programming: Linked Lists

Instructor: Hariom Pandya

Pandya has taught college programming,Web technologies and has a master's degree in Computer Engineering.

A linked list is a data structure used to create, update and/or delete similar, linked data at run time. There are four types of linked lists based on their structure: singly linked, circular linked, doubly linked and circular doubly linked. In this tutorial we will learn about the structure of singly linked lists and the steps to create and delete a node in a singly linked list.

Lesson Description: Linked Lists

Consider you have a large sorted list of data and you have to add randomly-generated data at specific locations in your sorted structure at run time. Also, consider that a user may request to remove any element from this list. To satisfy these needs, we obviously can't use an array. When we have multiple data of similar types as just described in which elements are added or deleted at run time, we use a linked list data structure.

One of the major advantages of linked lists over arrays is that we can add or delete data at run time which is the basic concept of dynamic memory. Also, consider that we may want to remove some element from the middle of existing data. Arrays need a rearrangement of all remaining elements while in linked lists, it's just an adjustment of addresses (pointers).

Array v/s Linked list (Courtesy : GeeksforGeeks.org)

Linked list provides following two advantages over arrays

1) Dynamic size

2) Ease of insertion/deletion

Linked lists have following drawbacks:

1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.

2) Extra memory space for a pointer is required with each element of the list.

3) Arrays have better cache locality that can make a pretty big difference in performance.

Lesson Overview & Knowledge Required

To understand linked lists easily, let's consider a train where the total number of compartments vary based on the number of passengers and they are controlled by the engine driver. All compartments are linked together and carry passengers.

A linked list is similar to this train where we refer to the compartments as nodes and the connections between them as links. Our linked list is controlled by a head pointer which points to the first node of the linked list. Every node of our linked list contains data (passengers) and the address (link) of the next node.

Below is the knowledge and skills required to complete this lesson and create the program in the C programming language:

  • Structures
  • While loops
  • Pointers


Linked List


Node Template

Let's try to code the linked list in C! We know that a node = data + address (of next node). For the simplicity of our code let's assume the data is an int data. The C structure to define the template of our node is:

struct node{
 int data;
 struct node *next;
}node1,node2,node3;

The above code defines a C structure type named node with two members: data (passenger) and next (address/link of the next node). This template will not allocate any memory unless we create a variable of it. (The data type of that variable should be struct node). So, at the end of code we have created three variables of node, i.e. node1, node2, node3.

{NOTE: This is one way to create variables statically. You can also use syntax datatype variable_name; to create static nodes. An alternate way is to create dynamic memory using functions like malloc(), calloc(). For now, we are not focusing on dynamic memory to create this simple application.}

Initialize all variables

The next step is to initialize the data and next member of every variable. We can achieve this by using . (dot) operation along with the variable name in C:

SYNTAX: variable_name.member_name

Let's first initialize the data member of all variables :

node1.data=5;
node2.data=23;
node3.data=3;

For now let's initialize the address member (next) as empty (NULL) for all variables.

node1.next=NULL;
node2.next=NULL;
node3.next=NULL;

OK, so our compartments (nodes) are ready. Let's link it together. For linking purposes, we need the following connection:

1) The first node must give us an address of the 2nd node.

2) The second node must give us an address of the 3rd node.

3) As of now, the third node is the last one so let it contain NULL. (This NULL represents an address of none.)

Let's code it :

node1.next=&node2;
node2.next=&node3;

{NOTE: You can directly set next member as an address of next node without prior initialization to NULL. But it is better practice to initialize all members before generating a linked list, especially when you use looping structure and dynamic memory to generate a bunch of nodes.}

Next, it is time to create a driver of our train ...the head pointer.

As the head needs to point to a node, it should be a pointer which can point to a structure node. The C code will be :

//Create Head Pointer
struct node *head;
//Head points to first node
head=&node1;
// Or alternatively : struct node *head=&node1;

So now our linked list is ready and it is exactly similar to our diagram. Next, let's try to perform insert and delete operations on this linked list.

Insert and Delete

The next functions that we will learn are related to insertions and deletions in a linked list. For simplicity, we will insert and delete nodes at the beginning only.

Insert

Steps to follow to insert a node at the beginning of the list:

1) Create a new node t.

2) Set next member of this newly-created node as head.

3) Reset head to t node.


Insert


struct node t;
t.data=70;
t.next=head;
head=&t;

Delete

Steps to follow to delete a node from the beginning of the list:

1) Store location of the first node into some temporary pointer tmp.

2) Move head pointer one step ahead so that it points to the next node.


Delete-LinkedList


struct node *tmp;
tmp=head;
//When you access member via pointer you have to use -> sign over .
head=head->next;

Final Code

Let's conclude the discussion by putting all of this together with a driver program (main()) .

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 160 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create An Account
Support