Introduction
For the assignment of unit 1:3, we were instructed to choose a complex technical term related to our field and provide the parenthetical, sentence and expanded definition of the term with at least three supporting sources cited. The definitions should be easily understood by an audience who lack knowledge of the term we are defining. The objective of this assignment is to allow us to appreciate the importance and role of definitions in technical writing, to understand how audience and purpose indicate the need for definition, to differentiate between the levels of details in definition, and to select the right level of detail according to the situation. I would like to acknowledge my teammate Jackson Kuan for his help in editing my work.
Situation
A university professor explaining the term linked list to second-year computer science students.
Parenthetical Definition
A linked list (a type of list data structure) can store data in a linear fashion while maintaining order.
Sentence Definition
A linked list is a linear data structure where each element stores a value and a pointer to the next element in the list.
Expanded Definition
In computer science, a linked list is a linear and dynamic data structure that stores a list of elements while retaining the order.
Analysis of Parts
Figure 1 shows a typical singly linked list which usually consists of a “head” pointer pointing to the first element and the list of nodes (elements in the linked list). Each node contains two pieces of data:
- the data of the current element (could be of any type: int, string, boolean etc.)
- a pointer or reference variable (usually named next) that points to the address of the next node.
The last node of the linked list points to NULL to indicate that you have reached the end of the list.
Figure 1. The basic structure of a singly linked list (Linked List Structure, n.d.)
Operating Principle
The three main operations you can do on a data structure are search, insertion and deletion.
Search:
To traverse through a linked list to find the element needed, a pointer (named “temp”) is made to point to the head of the list. When the current node does not contain the data we are looking for (temp.data != targetData), we set the “temp” pointer to the next node in the list (temp = temp.next). We repeat this process until we find the element we are looking for, or we reach the end of the list and the element does not exist in the list. (Kumar, n.d.)
Figure 2. Singly-linked list traversal [GIF image of linked list traversal]. (n.d.). procoding.org/linked-list/
Insertion:
Insertion of an element in the middle of a linked list is done by first traversing through the list to find the point of insertion, then change the pointer of the element before the point of insertion to point to the node being inserted and change the pointer of the node being inserted to point to the node after the point of insertion (Kumar, n.d.).
Figure 3. Singly-linked list insertion (Illustration of linked list insertion, n.d.)
Deletion:
The first step of deletion is done in a similar fashion. First, traverse through the list to find the node of deletion. Then, change the pointer of the previous element to point to the element after the node of deletion. Lastly, delete the node from the memory (Kumar, n.d.).
Figure 4. Singly-linked list deletion (Illustrations of linked list deletion, n.d.)
Compare and Contrast – Why linked list? Why not arrays?
Unlike an array which has fixed length and contiguous storage of elements in the memory accessed by indexes, a linked list data structure does not require the nodes to be stored in a continuous fashion in memory, and this enables many useful properties. A linked list can have dynamic size due to the ability to extend the linked list easily by adding the address of the next node to the last node in the list. (Linked list: Set 1 (introduction), 2022) The list can also be shortened by deleting the last node and setting the pointer of the second last node to NULL.
In addition, insertion and deletion of nodes in the middle of a linked list is done with much more ease than an array (Linked list: Set 1 (introduction), 2022). As shown previously, it is sufficient to simply manipulate the pointers of the element before and after the point of insertion/deletion. On the other hand, with arrays, insertions in the middle of the list requires shifting the rest of the array down in memory to make room for the insertion.
However, this data structure takes up more memory because each element carries one more piece of data than an array element – the address of the next node (Linked list: Set 1 (introduction), 2022). Also, every time you want to access a node, you will need to traverse through the list from the head to be able to find that node. Whereas for arrays, it is sufficient to know the index of the element (Linked list: Set 1 (introduction), 2022). Therefore, the choice of use is heavily dependent on the situation, and the advantages and disadvantages of each data structure should be weighed in each situation.
Code Snippet Example in Python
Figure 4a. Linked List Code Snippet
The node class contains two properties: data and next. The linked list class contains the head property. When this code snippet runs, a linked list (llist) and three nodes are created storing data 1, 2, 3. The head of the list is set to node with data 1.
Figure 4b. Linked List Code Snippet
Then the above two lines will “link” the nodes together by setting the next pointer on head (node1) to point to the second node (node2) and setting the next pointer on second node (node2) to point to the third node (node3).
In addition to the singly linked list that shown thus far, there are also other variations of the linked list. A doubly linked list has pointers both to the next element and to the previous element allowing two directional traversals. A circularly linked list links the last node to the head, allowing the list to form an endless “circle”.
Citation/References
Kumar, A. (n.d.). Linked list. Retrieved January 31, 2022, from https://www.procoding.org/linked-list/#insertion-at-given-position-in-the-Linked-list
Linked list data structure. (n.d.). Retrieved January 31, 2022, from https://www.geeksforgeeks.org/data-structures/linked-list/#circularLinkedList
Linked list: Set 1 (introduction). (2022, January 18). Retrieved January 31, 2022, from https://www.geeksforgeeks.org/linked-list-set-1-introduction/
Urgenthomework.com. (n.d.). Linked list deletion. Retrieved January 31, 2022, from https://www.urgenthomework.com/linked-list-deletion
Urgenthomework.com. (n.d.). Urgent Homework. Retrieved January 31, 2022, from https://www.urgenthomework.com/linked-list-insertion
Leave a Reply