gulp>> Doubly-Linked-List>> 返回
项目作者： anoopmoothedath

项目描述 ：
This is a C program for doubly linked list. Various operations done on the DLL are insertion (beginning, specific position, end), deletion (beginning & end), traversal and count of the nodes.
高级语言： C
项目地址: git://github.com/anoopmoothedath/Doubly-Linked-List.git
创建时间： 2020-01-30T16:57:47Z
项目社区：https://github.com/anoopmoothedath/Doubly-Linked-List
开源协议：
下载


Doubly-Linked-List

This is a C program for doubly linked list. This DLL program has various operations :

  • Insertion (at the beginning, at end & at specific position)
  • Deletion (from beginning & end)
  • Count of the nodes
  • Traversal of DLL

Algorithms

Insertion in the beginning

  1. insertAtBeginInDLL(NODE first, int x)
  2. Step-1: Allocate memory to the node temp.
  3. Step-2: Store an integer value into data field of node temp.
  4. Step-3: If first != NULL then goto Step-4 else goto Step-6.
  5. Step-4: Assign the address contained in the first node to the next field of temp.
  6. Step-5: Assign the address contained in the temp node to the prev field of first.
  7. Step-6: Now treat the temp node as first node.
  8. Step-7: Finally return the first node.

Insertion at the end

  1. insertAtEndInDLL(NODE first, int x)
  2. Step-1: Declare a NODE lastNode and assign first to it.
  3. Step-2: Allocate memory to the NODE temp.
  4. Step-3: Store an integer value into data field of NODE temp.
  5. Step-4: If the first is referenced to NULL then assign temp to first node.
  6.         Otherwise 
  7.             1. Traverse the list up to the last node (meaning the next field of a node contains Null).
  8.             2. Assign the temp node to next field of the lastNode and assign lastNode to prev field of temp.
  9. Step-4: Finally return the first node

Insert at specific position

  1. insertAtPositionInDLL(NODE first, int position, int x)
  2. Step-1: If position is less than or equal to 0 or (First == NULL && position > 1), Print "No such position in DLL so insertion is not possible" else go to Step-2.
  3. Step-2: Assign first to a node last.
  4. Step-3: Move the previous node of the last node of the given position by iteration when the given position is there in DLL,
  5.         Otherwise print "No such position in DLL so insertion is not possible" and return first node.
  6. Step-3: Allocate memory to the node temp.
  7. Step-4: Store an integer value into data field of node temp.
  8. Step-5: If the given pos is 1 then
  9.             If first != NULL then 
  10.                 1. Assign first to next field of temp node and next assign temp to prev field of first.
  11.             Otherwise
  12.                 1. Assign temp to first.
  13.         Otherwise if last == NULL then
  14.             1. Print  "No such position in DLL so insertion is not possible" and return first.
  15.         Otherwise
  16.             1. Assign next field of last to next field of temp node.
  17.             2. Assign last to prev filed of temp.
  18.             3. If next field of last != NULL , then assign temp to prev field of last->next.
  19.             4. Assign temp to next field of last .
  20. Step-6: Finally return the first node.

Delete from beginning

  1. deleteAtBeginInDLL(NODE first)
  2. Step-1: Assign first node to the node lastNode
  3. Step-2: If  next next field of lastNode equal to NULL [i.e It is the only node in the list] then make first equal to NULL [Making List Empty].
  4.         Otherwise
  5.             Assign next of first node to first [first will point to second node now].
  6.             Make first -> prev  to NULL [first node's prev should be NULL always].
  7. Step-3: Print "The deleted element from DLL : data field of lastNode".
  8. Step-4: Free the memory allocated to the lastNode node.
  9. Step-5: Return the first node

Delete from end

  1. deleteAtEndInDLL(NODE first)
  2. Step-1: Assign first node to the node lastNode.
  3. Step-2: If only one node in the list then assign NULL to first and goto Step-5, otherwise goto Step-3.
  4. Step-3: Traverse the list up to the last node of the list (meaning move lastNode to the last node of the list) 
  5.         and place temp node as previous of the lastNode.
  6. Step-4: Store NULL in the next field of temp.
  7. Step-5: print "The deleted element from DLL : data field of lastNode".
  8. Step-6: Free the memory space of lastNode.
  9. Step-7: Finally return the first node.

Count the nodes in DLL

  1. countInDLL(NODE first)
  2. Step-1: Assign the address contained in first node to temp node.
  3. Step-2: Initialize a variable sum to 0 (zero).
  4. Step-3: Repeat Step-4 and Step-5 until temp reaches the NULL .
  5. Step-4: Increment the sum by 1.
  6. Step-5: Move to the next node by placing the address of the next node in temp node.
  7. Step-6: Finally return sum.

Traversal

  1. traverseListInDLL(NODE first)
  2. Step-1: Assign the address contained in first node to lastNode node.
  3. Step-2: Repeat Step-3 and Step-4 until lastNode is NULL.
  4. Step-3: Print the data field of the lastNode.
  5. Step-4: Move to the next node by placing the address of the next node of lastNode into the lastNode node.
  6. Step-5: Finally print "NULL" at the end of the list.