Introduction to linked list

LINKED LIST IN C :-

           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

}