Understanding Linked List programming-3

We now know how to create data type for a node of a linked list and how to traverse linked list and to add nodes at various positions. In this post I am going to tell how to delete nodes at any position.

Deleting root node of linked list

Deleting a root node from a linked list is really a simple deal if you have read my previous posts. All you need to to do is:

1. Change the current node to the head node. 
2. Store the address of head node in a temporary variable of pointer type. 
3. Traverse to the immediate next node using current->next. 
4. Mark that node as head or root node.
5. Free the memory space occupied by previous head node using free() function.

The code for the same is:
                                     
                  current=head;
                  struct linkedlist *address;
                  address=head;
                  head=current->next;
                  free(address);

• The First line of code assigns head node as current node.
• The second line of code creates a temporary pointer variable address of type linkedlist.
• Next  head node address is assigned to the address variable which is needed as we have to later free up the space occupied by current head node
• Now we have changed the head node by immediate next node using current->next.
• Finally we free up the space occupied by previous head node.

Deleting any node from linked list

Deleting any node other than root node requires a couple of extra steps. The whole process to delete a node is explained in following steps:

1. Change the current node to head node.
2. Traverse to the node  just before the node required to be deleted.
3. Save the address of that node in some temporary variable (say 'address') of pointer of linkedlist structure type.
4. Move to the next node which is the one to be deleted that means now the current node is the node to e deleted.
5. Now change the pointer of next node with name 'address' to the pointer of the node pointed by current node. Now the address named node point to the node which was previously pointed out the the node to be deleted.
6. Finally free up the space occupied by deleted node.

The code snippet is as follows:
       struct linkedlist *address; 
       int position=1;
       current=head;
       while(current!=NULL && position<x)  
        {
         position++;
         address=current;
         current=current->next;
        }
        address->next=current->next;
        free(current);

Explanation:

• The First line of code creates a temporary pointer variable address of type linkedlist.
• The second line of code initializes a position variable position to 1 for traversing.
• The second line of code assigns head node as current node. 
• Next we loop till list is empty (Current !=NULL) or we reach position just before x.
• Inside the loop we change the address variable so that in the end address variable contains the address of node just before node to be deleted. We also set the current node as the node to be deleted using current=current->next expression.
• Finally we change the "next" pointer of  node name address with the "next" pointer of current (node to be deleted) node.
• Then free up the space occupied by the deleted node. 

Cheers!!! We are done with all the basic operations on a Linked list . You can get the complete program form the following link. Next we will continue with searching any node.

DOWNLOAD PROGRAM HERE

Mail me if the link has expired or not working
 

Understanding Linked List programming-2

Till now we have learned the data type to be used for linked list and creation of a root node of a singly linked list. In this article we will learn how to add nodes to a previous node.

Adding nodes to Linked List after last node

For adding node after the last node, we must first allocate a memory for that node, then change the pointer of previous node to our new last node. After that insert the value of new last node and make its pointer pointing to NULL. 

     struct linkedlist *newNode=(struct linkedlist*)malloc(sizeof(struct linkedlist));

     current->next=newNode;

     newNode->value=20;

     newNode->next=null;

     current=newNode;

Explanation

• The first line allocates memory for a new node in a similar way explained in previous post.
• The second line make the pointer of current last node to point to newly formed node.
• Third Line inserts an integer value of 20 in the new node.
• Next line of code makes the pointer of new node point to Null.
• Last line makes the new node to current node. 

Here in this we have presumed that the current node is the last node only. If not we have to make an extra step of traversing the last node. This will be explained later.

Traversing a linked list

Before we learn how to insert a node at specific location, we must understand how to traverse a linked list. Traversing a linked list is very simple. I will show the following piece of code which will traverse the linked list and print the current address of node, value of node and address of node current node is pointing to.

        current=head;
    while(current!=NULL)
     {
       printf("%p    %d   %p\n",current,current->value,current->next);
       current=current->next;
     }

Explanation

• The first line of above code assigns head node or root node as the current node so that we start traversing form the root node.
• Next I have started a while loop which will run until current node points to NULL. 
• Inside the loop, using printf(), I have printed current node address by using %p (for pointers) with current struct, value inside node by using %d with current->value and address of next node by using %p with current->next.
• Next I have changed the current node by making the address of current node  to that of the next node by current=current->next.

Adding node at given position

To insert node at a given location say n, first of all we need to traverse upto a node n-1. Then store the pointer value of that node. Then create a new node, insert the desired value in it. Then change the pointer of n-1 th node to point to newly created node.  Finally assign the previously saved pointer address to this newly created node. This is coded below.

       struct linkedlist *temp=(struct linkedlist*) malloc(sizeof(struct linkedlist));
   int data,position=1,x;
   int *address;

   printf("Enter the Location: ");

   scanf("%d",&x);   

   printf("Enter the data:");
   scanf("%d",&data);
   current=head;
   while(current!=NULL && position<x-1)
   {
    position++;
    current=current->next;
   }
   address=current->next;
   current->next=temp;
   temp->next=address;
   temp->value=data;
   current=temp;

Explanation

• First line of code allocates memory area for a new node named temp.
• Next I declared 3 integer variables. data for value to be stored in node, x for the position where the new node is to be inserted and initialized position to 1. position variable will help in location the desired position where the node is to be inserted.
• In the third line, an integer pointer has been created to hold the address of x-1 th node.
• In the next four lines of code, i have entered the value of data and x at run time.
• In the following line, I have made the head or root node as the current node to start traversing upto x-1th node.
• . The while loop will traverse until x-1 th node or last node if the specified position is not found.
•  In the next line the address pointed by current node that is currently the x-1th node is saved in the address variable.
• After that the address pointed by the x-1th node is changed to the address of new temp node.
• Next in temp node  the value of next which stores the value of next node is assigned the value stored in address variable.
• Following that the value field of temp is set to data.
• Finally the current node is set as the newly inserted temp node.

We can adopt similar procedure to insert the node in the beginning.

Understanding Linked List programming-1

Linked List s a data structure consisting of nodes linked to each other by pointers pointing to the address of next node in the list in a most simple case. The last node will point to a NULL pointer.
The concept is very simple but when it come to programming Linked lists, it always become a hard stone to break for me possibly due not not so much familiarity with the pointers. So here i am going to explain how to create programs on linked lists in a very convenient manner statring from the basics.

Defining Data type

Before proceeding, we must define a what data type should be convenient for defining a node in a linked list. A node contains a value and a memory address pointing to next node. So now its evident that we must define a data type rather than using existing ones to accommodate two different parts of node. The value part can be Integer or floating point number or even a character or string which can be defined by their respective traditional data types while the memory address can be defined by a pointer. These two can be grouped together in a structure which will define a user-defined data type for a single node.

                                  struct linkedlist

                   {

                      int value;

                      struct linkedlist *next;

                   };

The above structure named linked lists contains two declarations.

1. First one illustrates the  the value a node will hold. It has been declared as int. which constraints that linked list will hold only integer values. But you can make your linkedlist structure to hold values of different data types. This i will tell you in the later part of the series- Understanding Linked List programming. For now i want to make it as simple as possible.

2. The next one is a pointer to the next node which will hold the address of next node. Since the next node will have a similar data type, the pointer is of type linkedlist structure. Remember pointers do have types like int* ptr, void *ptr etc.

Creating first node of Linked list

To start creating a linked list, we must make sure that the list is empty. For this we must initialize the head node and current node as NULL. 

                               struct linkedlist *head=NULL;

              struct linkedlist *current=NULL;

The above two lines of code initializes head node as well as current node to NULL.

 Following lines of code shows how to create a root node.

               struct linkedlist *ptr=(struct linkedlist*)malloc(sizeof(struct linkedlist));

              

                 ptr->value=10;

                 ptr->next=NULL;

                 head=current=ptr;

               

 Explanation:

•  The first statement struct linkedlist *ptr=(struct linkedlist*)malloc(sizeof(struct linkedlist)); creates a pointer of type linkedlist and allocates a size equal to the size of structure linked list so that it can accommodate both the value and memory address. (struct linkedlist*) is used for casting. 
• The second statement ptr->value=10; assigns a value of 10 to value field of root node.

• The next statement ptr->next=NULL; assigns address of next node as NULL as currently only root node exists which points to no other node.
• The last statement assigns the memory address of head as well as current node as ptr. So that they can be accessed using memory address ptr.                      
   

   Adding nodes to the root node and deleting nodes from the linked list will be covered in the next post.     

Why I prefer AMD over Intel?

Whenever we are out to buy a new PC, Laptop or other computing device, after the brand name of the the product, next thing we look at is the processor. There are two majors in the processor market-Intel and AMD, and we decide among these two only and never bother to look at the third option. Most of us prefer to buy product with Intel processor probably due to its market value. But i still prefer AMD over Intel and i have some reasons to do so. Some of them mentioned below.

INTEL Vs AMD

Intel offer more clock frequency than AMD and hence perform faster than AMD.  Really???

Sorry Intel lovers but this is not the case. Without doubt Intel processors have more clock frequency than their AMD counterparts but AMD perform much more work per clock than an Intel processor. So an AMD processor working at 2.8 GHz is actually working faster than an Intel processor working at 4.0 GHz. Even if we talk about maximum frequencies available for intel and AMD processors, AMD is way head with their latest FX operating at 5.0 GHz and intel's latest 4th generation i7 processor operating at 3.60 GHz (that too with turbo boost technology).

The cost factor

With all one's heart, a similar performing AMD processor is much cheaper in cost than its Intel buddy.  and if we talk about latest products available till date, AMD FX is priced at $199.99 while Intels 4th generation i7-4950HQ will cost more than $280.

Technologies at offer by AMD

(1) HyperTransport- It is a technology for interconnection of computer processors. It is a bidirectional serial/parallel high-bandwidth, low latency point to point link. it is used by IBM, Apple and other majors. It makes quick access times to system I/O for better performance. Intel is also catching up with its QuickPath interconnect technology.

(2) Integrated DRAM Controller with AMD Memory Optimizer- A high-bandwidth, low-latency integrated memory controller having support for up to DDR3-1866. Also supports new low voltage memories of 1.35V and 1.2V. It offers Direct communications to each core in Dual-Core module. Thus Optimizes memory controller to feed more cores. No such similar technology is available with Intel as of yet.

(2) AMD Turbo CORE- It provides new instruction capabilities for performing heavy floating point calculation accurately and speedily. It also offers Advanced Encryption Standard noticeably increase performance on the latest encryption applications. No such similar technology is available with Intel as of yet.

(3) AMD Virtualization- It helps virtualization software to run more securely and efficiently enabling a better experience when dealing with virtual systems. Intel is also able to do so but quite less efficiently.

 (4) AMD PowerNow! (Cool'n'Quiet)- It offer users to get more efficient performance and consuming less power by dynamically activating or turning off parts of the processor. By this the haeting problem of AMD is undone. Intel processors are usually quieter and PowerNow is big challenge overcome from Intel.

Technologies at offer by Intel

(1) Hyper-Threading- Hyper-Threading Technology uses resources efficiently, enabling multiple threads to run on each core and increasing processor throughput. There is no such AMD's counterpart as of now but still latest from AMD can run more threads in a single processor if not a single core.

(2) Turbo Boost-It  automatically allow cores to run faster than the base operating frequency at cost of drawing more power. In some cases it also make the system unstable, more heating of processor.

(3) QuickPath InterConnect- A point-to-point processor interconnect technology designed to compete with AMD's HyperTransport technology which is in the market before.

(4) Tri-Gate (3D) Transistors- It enables quick transition between on-off states of gates, thus increasing more clock frequency. AMD is catching up soon. Even without this technology AMD has been able to perform at 5.0 Ghz.

Factors in favor of Intel

The various benchmarks over internet suggest that per core performance of Intel's processor is better than AMD. But if you look at performance per cost ratio, AMD definitely has upper hand.


Note: I am not any AMD product promoter or employee. The information above is collected from internet and is based on my experience with Intel and AMD processors. Intel processors may have other advantages above the purview of my knowledge.