Linked list
Background
Linked list (March. 18, 2016, 11:40 UTC). In Wikipedia: The Free Encyclopedia. Retrieved from [1]
In computer science, a linked list is a linear collection of data elements, called nodes pointing to the next node by means of pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.
A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.
Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including list (the abstract data type), stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.
The principal benefit of a linked list over a conventional array data structure|array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while an array has to be declared in the source code, before compiling and running the program. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.
On the other hand, simple linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list (assuming that the last node is not maintained as separate node reference in the list structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require sequential scanning of most or all of the list elements. The advantages and disadvantages of using linked lists are given below.
Advantages
- Linked lists are a dynamic data structure, which can grow and be pruned, allocating and deallocating memory while the program is running.
- Insertion and deletion node operations are easily implemented in a linked list.
- Linear data structures such as stacks and queues are easily executed with a linked list.
- They can reduce access time and may expand in real time without memory overhead.
Disadvantages
- They have a tendency to use more memory due to pointers requiring extra storage space.
- Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
- Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
- Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer.
Module structure
<source lang="fortran">
!! Module for linked list.
MODULE linked_list_module
USE list_data_module,ONLY: LIST_DATA IMPLICIT NONE
!!! The element of the list. TYPE,PRIVATE :: LINKED_LIST TYPE(LINKED_LIST), POINTER :: next TYPE(LIST_DATA) :: DATA END TYPE LINKED_LIST
!!! Struct for linked list. TYPE linked_list_struct !!! pointer to the head of the list. TYPE(LINKED_LIST),POINTER :: head
CONTAINS
PROCEDURE :: init !!!() constructor of the struct.
PROCEDURE :: size !!!() RESULT(SIZE of the list).
!!! Return the size of the list.
!!! If list is empty, return 0.
PROCEDURE :: add_head !!!(DATA)
!!! Add data to the front of the list.
PROCEDURE :: add_tail !!!(DATA)
!!! Add data to the end of the list.
PROCEDURE :: take_head !!! () RESULT(head_DATA)
PROCEDURE :: take_tail !!! () RESULT(tail_DATA)
!!! Be careful with the size of the list.
!!! Program will stop if the list is empty
!!! while these functions are called.
!
PROCEDURE :: is_empty !!!() RESULT(T/F)
!!! See if the list is empty.
!!! Return .TRUE. if it is.
!
PROCEDURE :: empty !!!() RESULT(T/F)
!!! Empty current list.
!!! Returns .FALSE. if the list is already empty.
!!! Otherwise returns .TURE.
!
PROCEDURE,PRIVATE :: locate !!! (key) RESULT(loc)
!!! Return the pointer to the position of DATA.
!!! If multiple DATA have the same key, return position
!!! of the first one.
!!! If DATA with the same key does not exist, return NULL pointer.
!
PROCEDURE :: has !!! (key) RESULT(T/F)
!!! Check if DATA with the same key exists in the list.
!!! Returns .TRUE. if at least one exists.
!!! Returns .FALSE. otherwise.
!
PROCEDURE :: get !!! (key) RESULT(DATA)
!!! Return DATA with given key.
!!! If key not found, print a warning and return a DATA with
!!! a value of "NaN".
!
PROCEDURE :: add !!! (DATA) RESULT(T/F)
!!! Add data with unique key.
!!! If DATA with the same key doesn't exist then add data to the
!!! tail of the list and return .TRUE.
!!! If the DATA with the same key already exists,return .FALSE.
!!! and overwrite the value with the new one.
!
PROCEDURE :: add_no_overwrite !!! (DATA) RESULT(T/F)
!!! Same as add except that overwriting is disabled.
!
PROCEDURE :: overwrite !!! (DATA) RESULT(T/F)
!!! Overwrite data with given key.
!!! If DATA with the same key exsits, over write the value
!!! and return .TRUE.
!!! If DATA with the same key doesn't exist, return .FALSE.
!
PROCEDURE :: delete !!! (key) RESULT(T/F)
!!! Delete data with given key.
!!! If DATA exists and deletion succeeds, return .TRUE.
!!! Otherwise, return .FALSE.
!!! If there are multiple DATA with the same key, delete the
!!! first found and return .TRUE.
!
PROCEDURE :: delete_all !!! (key) RESULT(T/F)
!!! Delete all DATA that share the same key.
!!! Return .TRUE. if at least one deletion is successful.
!!! Otherwise, return .FALSE.
!
PROCEDURE :: copy !!! (list)
!!! Copy the given list to current one.
!!! Note that initialization is required before calling this.
!
PROCEDURE :: combine !!!(list)
!!! This subroutine combines the list with the given one.
!!! For best performace, the combine is based on
!!! add_head() operations.
!!!
!!! Example :
!!! self=> A->B->C
!!! list=> D->E->F
!!! The result of combine() operation:
!!! self=> F->E->D->A->B->C
!
PROCEDURE :: divide !!!(back)
!!! This subroutine divides the list into 2 halves.
!!! If the length of list is odd, the extra node will
!!! go in the front list.
!!! Uses the fast/slow pointer strategy.
!
PROCEDURE :: print !!!()
!!! Print all the elements of the list onto screen.
!!! For debugging purposes only.
!
!!!**** These 2 sorting subroutines are not part of the struct. ***!!!
!PROCEDURE :: sort_key !!!(list)
!!! Sort the list in ascending order of data%key.
!
!PROCEDURE :: sort_val !!!(list)
!!! Sort the list in ascending order of data%val.
!
!PROCEDURE :: merge_key !!!(a,b) RESULT(head_loc)
!!! Merge two lists in ascending order of data%key into list.
!!! And return the pointer to the head of new list.
!
!PROCEDURE :: merge_val !!!(a,b) RESULT(head_loc)
!!! Merge two lists in ascending order of data%val into list.
!!! And return the pointer to the head of new list.
!
FINAL :: destroy !!!() destructor.
!!-----------------------PRIVATE----------------------!!
!!====================================================!!
!!-----------------------PRIVATE----------------------!!
END TYPE linked_list_struct
CONTAINS
</source>