###Linked List - A heir of List :: Linear Data Structure, Abstract in nature
A Data Structure formed by group of nodes, each containing some data attribute along with a reference to another node of similar kind. A
nodeis an elementary block of linked-list and is dynamically allocated. Thus unlike arrays, linked-list have no fixed length and is only restricted to amount of memory pool available to the system (which of-course is virtually unlimited in modern days system).
- The variable START always points to the start of the list, i.e. First Element.
- The method new_node allocates a memory space for a new node.
- The attribute next of a node holds a reference(link) to another node.
Since abstract, the implementation can vary and so can the algorithm. One provided here is not meant for efficiency, but for basic implementation.
INSERT_AT_FIRST(LINKED_LIST p, element_to_insert):
IF START == NULL:
/* There's no element in the list */
START = new_node()
START.data = element_to_insert
START.next = NULL /* there's no more node after this */
ELSE
/* In case there are elements in the list */
q = new_node()
q.data = element_to_insert
/* append the existing list to this node */
q.next = START
/* update starting node */
START = q
END IF
END INSERT_AT_FIRST
INSERT_AT_LAST(LINKED_LIST START, element_to_insert):
IF START == NULL:
/* There's no element in the list */
START = new_node()
START.data = element_to_insert
START.next = NULL /* there's no more node after this */
ELSE
/* In case there are elements in the list */
q = START
/* Traverse to the last element of the list */
WHILE q.next != NULL :
q = q.next
END WHILE
q.next = new_elements() /* allocate a space */
q = q.next /* Move to new node */
q.data = element_to_insert
q.next = NULL /* there's no more node after this */
END IF
END INSERT_AT_LAST
INSERT_AT_POSITION(LINKED_LIST p, element_to_insert, position):
IF START == NULL OR position == 1:
p = START
/* If there are no previous element, p will contain NULL */
/* If there are some, then p will be holding their initial address */
START = new_node()
START.data = element_to_insert
START.next = p /* append the content of p */
ELSE
p = START
i = 1
WHILE p != NULL && i < position :
q = p
p = p.next
i = i + 1
END WHILE
IF p == NULL AND i < position:
PRINT "Invalid index. Current List size: " + (i - 1)
ELSE
r = new_node()
r.data = element_to_insert
q.next = r /* append this node to the node at position - 1 */
r.next = p /* store the rest of the list(after position) in new node's next */
END IF
END IF
END INSERT_AT_POSITION
DELETE_FROM_FIRST(LINKED_LIST START):
IF START != NULL:
p = START /* save the node to delete */
element_deleted = p.data
START = p.next /* update starting node */
FREE(p) /* deallocates the assigned memory space */
RETURN element_deleted
ELSE
/* List's empty. No elements to delete. */
PRINT "Underflow"
END IF
END DELETE_FROM_FIRST
DELETE_FROM_LAST(LINKED_LIST START):
IF START != NULL:
IF START.next == NULL:
/* Only element in the list */
element_deleted = START.data
FREE(START) /* deallocates the assigned memory space */
START = NULL
ELSE
p = START
WHILE p.next != NULL:
q = p
p = p.next
END WHILE
/* At the end of loop, p will hold the last node */
/* and q will be holding the node prior to the last node */
element_deleted = p.data
q.next = NULL /* de-link the last node */
FREE(p) /* deallocates the assigned memory space */
END IF
RETURN element_deleted
ELSE
/* List's empty. No elements to delete. */
PRINT "Underflow"
END IF
END DELETE_FROM_LAST
DELETE_FROM_POSITION(LINKED_LIST START, position):
IF START != NULL:
p = START
IF position == 1:
START = START.next
ELSE
i = 1
WHILE p.next != NULL && i < position:
q = p
p = p.next
i = i + 1;
END WHILE
/* After the loop, p will hold the node at position defined */
/* and q will be holding the node prior to the node p, i.e. position - 1 */
IF p.next == NULL AND i < position:
PRINT "Invalid index. Current list size: " + i
ELSE
q.next = p.next /* de-link this node from the list */
END IF
END IF
element_deleted = p.data
FREE(p) /* deallocates the assigned memory space */
RETURN element_deleted
ELSE
/* List's empty. No elements to delete. */
PRINT "Underflow"
END IF
END DELETE_FROM_POSITION
TRAVERSE(LINKED_LIST START):
IF START != NULL :
/* We can easily iterate over the nodes to access them */
FOR p = START TO p.next != NULL:
PRINT node p
END FOR
ELSE
/* List's empty. No elements to visit. */
PRINT "No elements in the list"
END IF
END TRAVERSE
REVERSE(LINKED_LIST START):
IF START != NULL :
p = START
r = NULL
WHILE p.next != NULL :
r = q
q = p
p = p.next
q.next = r
END WHILE
START = p
ELSE
/* List's empty. No elements to reverse. */
PRINT "No elements in the list"
END IF
END REVERSE
For most of the operations here, the complexity will be in order of O(k) [0 < k <= n], where n denotes the Stack size during the concerned moment. Specifically,
- INSERT_AT_LAST, DELETE_FROM_LAST, TRAVERSE and REVERSE will be strictly of O(n)
- On a sound condition, INSERT_AT_FIRST and DELETE_FROM_FIRST should be of O(1)
- while INSERT_AT_POSITION, DELETE_FROM_POSITION will be of O(k)
[k is the position, 0 < k <= n].