{"id":515,"date":"2021-06-09T01:08:20","date_gmt":"2021-06-09T01:08:20","guid":{"rendered":"https:\/\/xcodeph.net\/?page_id=515"},"modified":"2021-06-09T01:16:38","modified_gmt":"2021-06-09T01:16:38","slug":"linked-list","status":"publish","type":"page","link":"https:\/\/xcodeph.net\/index.php\/linked-list\/","title":{"rendered":"Linked List"},"content":{"rendered":"\n

Is a data structure that makes it easy to rearrange data without having to move data in memory.<\/p>\n\n\n\n

A linear collection of specially designed data elements, called nodes, linked to one another by means of pointers.<\/p>\n\n\n\n

Parts of node<\/strong><\/h2>\n\n\n\n


1. Contains the information of the element (data).
2. Contains the address of the next node in the linked list (next).<\/p>\n\n\n\n

\"100<\/figure>\n\n\n\n
\"start
NODE<\/figcaption><\/figure>\n\n\n\n
\"\"
Linked list representation of integers<\/figcaption><\/figure>\n\n\n\n

Linked list advantages<\/strong><\/h2>\n\n\n\n
  1. Linked list are dynamic data structure. That is, they can grow or shrink during the execution of a program.<\/li>
  2. Efficient memory utilization: In linked list (or dynamic)representation, memory is not pre-allocated. Memory is allocated whenever it is required. And it is deallocated (or removed) when it is not needed.<\/li>
  3. Insertion and deletion are easier and efficient. Linked list provides flexibility in inserting a data item at a specified position and deletion of a data item from the given position.<\/li>
  4. Many complex applications can be easily carried out with linked list.<\/li><\/ol>\n\n\n\n

    Linked list disadvantages<\/strong><\/h2>\n\n\n\n
    1. More memory: to store an integer number, a node with integer data and address field is allocated. That is more memory space is needed.<\/li>
    2. Access to an arbitrary data item is little bit cumbersome and also time consuming.<\/li><\/ol>\n\n\n\n

      Linked List Operations<\/strong><\/h2>\n\n\n\n

      Creation<\/strong><\/p>\n\n\n\n

      Create a linked list. Once a linked list is created with one node, insertion operation can be used to add more elements in a node.<\/p>\n\n\n\n

      Insertion<\/strong><\/p>\n\n\n\n

      Insert a new node at any specified location in the linked list (beginning, end, or specified position between linked list).<\/p>\n\n\n\n

      Deletion<\/strong><\/p>\n\n\n\n

      Delete an item (or node) from the linked list (beginning, end, specified location of the linked list)<\/p>\n\n\n\n

      Traversing<\/strong><\/p>\n\n\n\n

      Process of going through all the nodes from one end to another end of the linked list. In singly linked list we can visit from left to right, forward traversing is nodes only. In doubly linked list forward and backward traversing is possible.<\/p>\n\n\n\n

      Searching<\/strong><\/p>\n\n\n\n

      Search values from the linked list.<\/p>\n\n\n\n

      Concatenation<\/strong><\/p>\n\n\n\n

      Appending the second list to the end of the first list.<\/p>\n\n\n\n

      <\/p>\n\n\n\n

      Types of linked list<\/strong><\/h2>\n\n\n\n

      Singly  Linked List<\/strong><\/p>\n\n\n\n

      Enables a program to move through the list in one direction, which is usually from the front of the list moving to the end of the list.<\/p>\n\n\n\n

      \"\"
      Creation (3 nodes with data value of 10, 20, and 30)<\/figcaption><\/figure>\n\n\n\n
      \"\"
      Insertion (insert node with data value of 5 at the beginning)<\/figcaption><\/figure>\n\n\n\n

      Linked list sample program<\/strong><\/h2>\n\n\n\n
      \n#include <iostream>\nusing namespace std;\n\nstruct node{\n\tint data;\n\tnode *next;\n};\n\nnode *start;\n\nvoid createList(int d);\nvoid AddBegin(int d);\nvoid display();\n\nint main()\n{\n\tstart = NULL;\n\tint n,m;\n\n\tcout << \"\\n\\nHow many nodes you want: \";\n\tcin >> n;\n\tfor(int i=0;i<n;i++) {\n\t\tcout << \"\\nEnter the element: \";\n\t\tcin >> m;\t\t\n\t\tcreateList(m);\n\t}\n\n\tdisplay();\n\tAddBegin(100);\n\n\tdisplay();\n\tcin.ignore().get();\n\treturn 0;\n}\n\nvoid AddBegin(int d)\n{\n\tnode *tmp;\n\ttmp = new node;\n\ttmp -> data = d;\n\ttmp -> next = start;\n\tstart = tmp;\n}\n\nvoid display()\n{\t\n\tnode *q;\n\tif(start==NULL){\n\t\tcout << \"\\n\\nList is empty\";\n\t\treturn;\n\t}\n\tq=start;\n\tcout << \"\\n\\nList is: \";\n\twhile(q!=NULL){\n\t\tcout << q->data << \" \";\n\t\tq=q->next;\n\t}\n\tcout << \"\\n\";\n}\n\nvoid createList(int d)\n{\n\tnode *q, *tmp;\n\ttmp = new node;\n\ttmp -> data = d;\n\ttmp -> next = NULL;\n\tif(start==NULL) {\n\t\tstart = tmp;\n\t} else {\n\t\tq = start;\n\t\twhile(q->next!=NULL)\n\t\t\tq = q->next;\n\t\tq->next = tmp;\n\t}\t\n}<\/pre>\n\n\n\n
      Singly Linked List<\/strong><\/h2>\n\n\n\n
      \n\/*\nProgram: Singly Linked Queue\n\n*\/\n\n#include <iostream>\n#include <iomanip>\nusing namespace std;\n\nstruct node{\n\tint data;\n\tnode *next;\n}*head;\n\nvoid createlist(int);\nvoid addbegin(int);\nvoid addafter(int,int);\nvoid display();\nvoid del(int);\nvoid delfirstelem();\nvoid count();\nvoid reverse();\nvoid search(int);\n\nint main()\n{\n\twhile(1)\n\t{\n\t\tint choice;\n\t\tsystem(\"cls\");\n\t\tcout << \"[1] - Create a list\\n\";\n\t\tcout << \"[2] - Add at the beginning\\n\";\n\t\tcout << \"[3] - Add after\\n\";\n\t\tcout << \"[4] - Delete\\n\";\n\t\tcout << \"[5] - Display\\n\";\n\t\tcout << \"[6] - Count\\n\";\n\t\tcout << \"[7] - Reverse\\n\";\n\t\tcout << \"[8] - Search\\n\";\n\t\tcout << \"[9] - Exit\\n\";\n\t\tcout << \"===================\\n\";\n\t\tcout << \"Enter your choice: \";\n\t\tcin >> choice;\n\t\tint n, num, pos;\n\t\tswitch(choice){\n\t\t\tcase 1:\n\t\t\t\tcout << \"\\nHow many node you want: \";\n\t\t\t\tcin >> n;\n\t\t\t\tcout << \"\\nEnter \" << n << \" element(s)\\n\";\n\t\t\t\tfor(int i=0;i<n;i++)\n\t\t\t\t{\n\t\t\t\t\tcin >> num;\n\t\t\t\t\tcreatelist(num);\n\t\t\t\t}\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 2:\n\t\t\t\tcout << \"\\nEnter a number (add at beginning)\";\n\t\t\t\tcin >> num;\n\t\t\t\taddbegin(num);\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 3:\n\t\t\t\tcout << \"\\nEnter the value and position of your element: \";\n\t\t\t\tcin >> num >> pos;\n\t\t\t\taddafter(num,pos);\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 4:\n\t\t\t\tcout << \"\\nEnter the value to be deleted from the list: \";\n\t\t\t\tcin >> num;\n\t\t\t\tdel(num);\n\t\t\t\t\/\/cout << \"delete first element \";\n\t\t\t\t\/\/delfirstelem();\n\t\t\t\tsystem(\"pause>0\");\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 5:\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 6:\n\t\t\t\tcount();\n\t\t\t\tbreak;\n\t\t\tcase 7:\n\t\t\t\treverse();\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 8:\n\t\t\t\tcout << \"\\nEnter the value to search: \";\n\t\t\t\tcin >> num;\n\t\t\t\tsearch(num);\n\t\t\t\tbreak;\n\t\t\tcase 9:\n\t\t\t\texit(1);\n\t\t\tdefault:\n\t\t\t\tcout << \"\\nWrong choice!\\n\";\n\t\t}\n\t\tcout << endl;\n\t\tsystem(\"pause\");\n\t}\t\n\treturn 0;\n}\n\nvoid delfirstelem()\n{\n\tnode *tmp;\n\ttmp=head;\n\thead=tmp->next;\n\tdelete tmp;\n}\n\n\n\/\/creation\nvoid createlist(int n)\n{\n\tnode *p, *tail;\n\ttail = new node;\n\ttail->data = n;\n\ttail->next = NULL;\n\tif(head==NULL)\n\t\thead=tail;\n\telse\n\t{\n\t\tp=head;\n\t\twhile(p->next!=NULL)\n\t\t\tp=p->next;\n\t\tp->next = tail;\n\t}\n}\n\n\/\/add begin\nvoid addbegin(int n)\n{\n\tnode *tmp;\n\ttmp = new node;\n\ttmp->data = n;\n\ttmp->next = head;\n\thead=tmp;\n}\n\n\/\/add after\nvoid addafter(int n,int pos)\n{\n\tnode *tmp, *p;\n\n\tif(head==NULL)\n\t{\n\t\tcout << \"You have to create first the linked list\\n\";\n\t\treturn;\n\t}\n\n\tp=head;\n\tfor(int i=0;i<pos-1;i++)\n\t{\n\t\tp=p->next;\n\t\tif(p==NULL)\n\t\t{\n\t\t\tcout << \"There are less than \"<<pos<<\" elements\";\n\t\t\treturn;\n\t\t}\n\t}\n\ttmp = new node;\n\ttmp->next = p ->next;\n\ttmp->data = n;\n\tp->next = tmp;\n\n}\n\nvoid del(int n)\n{\n\tnode *tmp,*p;\n\t\/\/delete at the beginning\n\tif(head==NULL)\n\t{\n\t\tcout << \"You have to create first the linked list\\n\";\n\t\treturn;\n\t}\n\tif(head->data == n)\n\t{\n\t\ttmp = head;\n\t\thead = head->next;\n\t\tdelete tmp;\n\t\treturn;\n\t}\n\tp=head;\n\t\/\/delete in between\n\twhile(p->next->next!=NULL)\n\t{\n\t\tif(p->next->data == n)\n\t\t{\n\t\t\ttmp = p->next;\n\t\t\tp->next = tmp->next;\n\t\t\tdelete tmp;\n\t\t\treturn;\n\t\t}\n\t\tp=p->next;\n\t}\n\tif(p->next->data == n)\n\t{\n\t\ttmp = p->next;\n\t\tdelete tmp;\n\t\tp->next=NULL;\n\t\treturn;\n\t}\n\tcout << \"\\nElement \" << n << \" not found\\n\";\n}\n\n\/\/count\nvoid count()\n{\n\tnode *p;\n\tp=head;\n\tint cnt=0;\n\twhile(p!=NULL)\n\t{\n\t\tp=p->next;\n\t\tcnt++;\n\t}\n\tcout << \"There are \" << cnt <<\" elements is the list\\n\";\n}\n\nvoid reverse()\n{\n\tnode *p1, *p2, *p3;\n\t\/\/for one element only\n\tif(head->next==NULL)\n\t\treturn;\n\tp1=head;\n\tp2=p1->next;\n\tp3=p2->next;\n\tp2->next=p1;\n\tp1->next=NULL;\n\n\twhile(p3!=NULL)\n\t{\n\t\tp1=p2;\n\t\tp2=p3;\n\t\tp3=p3->next;\n\t\tp2->next=p1;\n\t}\n\thead=p2;\n}\n\nvoid search(int n)\n{\n\tnode *p;\n\tp=head;\n\tint pos=1;\n\twhile(p!=NULL)\n\t{\n\t\tif(p->data==n)\n\t\t{\n\t\t\tcout << \"The element value \"<<n<<\" found at position \"<< pos;\n\t\t\treturn;\n\t\t}\n\t\tpos++;\n\t\tp=p->next;\n\t}\n\tcout << \"The element value \"<<n<<\" is not found\\n\";\n}\n\n\/\/display\nvoid display()\n{\n\tnode *p;\n\tif(head==NULL)\n\t{\n\t\tcout << \"List is empty!\\n\";\n\t\treturn;\n\t}\n\tp=head;\n\tcout << endl;\n\tcout << setw(20) << \"POINTER\" << setw(20) << \"DATA\" << setw(20) << \"NEXT\" << endl;\n\twhile(p!=NULL)\n\t{\n\t\tcout << setw(20) << p << setw(20) << p->data << setw(20) << p->next << endl;\n\t\tp = p->next;\n\t}\n\tcout << endl;\n}<\/pre>\n\n\n\n
      Doubly Linked list<\/strong><\/h2>\n\n\n\n
      #include <iostream>\n#include <iomanip>\nusing namespace std;\n\nstruct node{\n\tint data;\n\tnode *next;\n\tnode *prev;\n}*start;\n\n\/\/typedef node *NODE;\n\nvoid display()\n{\n\tnode *p;\n\tif(start==NULL)\n\t{\n\t\tcout << \"List is empty!\\n\";\n\t\treturn;\n\t}\n\tp=start;\n\tcout << endl;\n\tcout << setw(10) << \"ADDRESS\" << setw(15) << \"PREV\" <<setw(15) << \"DATA\" << setw(20) << \"NEXT\" << endl;\n\twhile(p!=NULL)\n\t{\n\t\tcout << setw(10) << p << setw(15) << p->prev <<setw(15) << p->data << setw(20) << p->next << endl;\n\t\tp = p->next;\n\t}\n\tcout << endl;\n}\nvoid createlist(int n)\n{\n\tnode *p, *end;\n\tend = new node;\n\tend->data = n;\n\tend->next = NULL;\n\t\n\tif(start==NULL)\n\t{\n\t\tend->prev=NULL;\n\t\tstart=end;\n\t}\n\telse\n\t{\n\t\tp=start;\n\t\twhile(p->next!=NULL)\n\t\t\tp=p->next;\n\t\tp->next = end;\n\t\tend->prev = p;\n\t}\n}\n\nvoid reverse()\n{\n\tnode *p1, *p2;\n\tp1=start;\n\tp2=p1->next;\n\tp1->next=NULL;\n\tp1->prev = p2;\n\twhile(p2!=NULL)\n\t{\n\t\tp2->prev=p2->next;\n\t\tp2->next=p1;\n\t\tp1=p2;\n\t\tp2=p2->prev;\n\t}\n\tstart=p1;\n}\n\nint main()\n{\n\twhile(1)\n\t{\n\t\tint choice;\n\t\tsystem(\"clear\");\n\t\t\/\/system(\"cls\");\n\t\tcout << \"[1] - Create a list\\n\";\n\t\tcout << \"[2] - Display\\n\";\n\t\tcout << \"[3] - Reverse\\n\";\n\t\tcout << \"[4] - Exit\\n\";\n\t\tcout << \"===================\\n\";\n\t\tcout << \"Enter your choice: \";\n\t\tcin >> choice;\n\t\tint n, num, pos;\n\t\tswitch(choice){\n\t\t\tcase 1:\n\t\t\t\tcout << \"\\nHow many node you want: \";\n\t\t\t\tcin >> n;\n\t\t\t\tcout << \"\\nEnter \" << n << \" element(s)\\n\";\n\t\t\t\tfor(int i=0;i<n;i++)\n\t\t\t\t{\n\t\t\t\t\tcin >> num;\n\t\t\t\t\tcreatelist(num);\n\t\t\t\t}\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 2:\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 3:\n\t\t\t\treverse();\n\t\t\t\tdisplay();\n\t\t\t\tbreak;\n\t\t\tcase 4:\n\t\t\t\texit(1);\n\t\t\tdefault:\n\t\t\t\tcout << \"\\nWrong choice!\\n\";\n\t\t}\n\t\tcout << endl;\n\t\tcin.ignore().get();\n\t\t\n\t\tsystem(\"pause\");\n\t}\t\n\treturn 0;\n\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"
      Is a data structure that makes it easy to rearrange data without having to move data in memory. A linear collection of specially designed data elements, called nodes, linked to one another by means of pointers. Parts of node 1. Contains the information of the element (data).2. Contains the address of the next node in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/515"}],"collection":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/comments?post=515"}],"version-history":[{"count":2,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/515\/revisions"}],"predecessor-version":[{"id":524,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/515\/revisions\/524"}],"wp:attachment":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/media?parent=515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}