LINKED LIST IN C :-
List means a sequence of items arranged one after another.
List means a sequence of items arranged one after another.
- A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence.
- Successive elements are connected by pointers.
- Last element points to NULL.
- It can grow ( during insertion) or shrink in size (in deletion) during execution of a program.
- It can be made just as long as required.
- It does not waste memory space. Dynamic memory allocation is often used in linked list.
- Linked lists were developed in 1955–1956 by Allen Newell, Cliff Shaw and Herbert A. Simon at RAND Corporation as the primary data structure for their Information Processing Language. IPL was used by the authors to develop several early artificial intelligence programs, including the Logic Theory Machine, the General Problem Solver, and a computer chess program.
- LISP, standing for list processor, was created by John McCarthy in 1958 while he was at MIT and in 1960 he published its design in a paper in the Communications of the ACM, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". One of LISP's major data structures is the linked list.
Some Basic Terminology:-
1. malloc() :- malloc() is a system function which allocates a block of memory in the "heap" and returns a pointer to the new block. The prototype for malloc() and other heap functions are in stdlib.h.
2. free() :- free() is the opposite of malloc.
Creating linked list :-
Node :- The type for the nodes which will make up the body of the list.
These are allocated in the heap. Each node contains a single client data
element and a pointer to the next node in the list.
struct node {
int data;
struct node* next;
} *head, *temp;
A simple baby example of linked list :-
struct node* BuildOneTwoThree()
{
struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;
head = malloc(sizeof(struct node)); // allocate 3 nodes in the heap
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));
head->data = 1; // setup first node
head->next = second; // note: pointer assignment rule
second->data = 2; // setup second node
second->next = third;
third->data = 3; // setup third link
third->next = NULL;
}
INSERTION IN BEGINNING OF A LINKED LIST
Now we will insert data in beginning of the linked list in a temporary variable 'temp' and after insertion we will assign the value of temp in 'head' variable.
Logic:- As we go on inserting data in temp , new temp node data should be assigned into head.
Function:-
struct node
{
int data;
struct node* next;
}*head,*temp; // global variable, can be accessed anywhere
void insert(int x)
{
temp=malloc(sizeof(struct node));
temp->data=x;
temp->next=head; //give the link part to previous head node
head=temp; //now assign newly created node as head
}
