Discussion Board # 2

Linked List

[Author Name(s), First M. Last, Omit Titles and Degrees]

[Institutional Affiliation(s)]

Linked List

Linked lists represent a type of data structure in which every element represents an object. A single object in a linked list is called a node. A node comprises of two parts. One is the data, and the other is the reference to the next location i.e., node. The first object in the list is the head, while the last is the tail. A linked list is an upgraded form of arrays. An array only allocates contiguous memory locations ADDIN ZOTERO_ITEM CSL_CITATION {"citationID":"cju24KD4","properties":{"formattedCitation":"(Sravani et al., 2017)","plainCitation":"(Sravani et al., 2017)","noteIndex":0},"citationItems":[{"id":42,"uris":["http://zotero.org/users/local/WKtM8IGm/items/JC7UD7BX"],"uri":["http://zotero.org/users/local/WKtM8IGm/items/JC7UD7BX"],"itemData":{"id":42,"type":"paper-conference","title":"Analyzing the linked list complexity using correlation methods","container-title":"2017 International Conference on Trends in Electronics and Informatics (ICEI)","publisher":"IEEE","publisher-place":"Tirunelveli","page":"1127-1130","source":"DOI.org (Crossref)","event":"2017 International Conference on Trends in Electronics and Informatics (ICOEI)","event-place":"Tirunelveli","URL":"http://ieeexplore.ieee.org/document/8300888/","DOI":"10.1109/ICOEI.2017.8300888","ISBN":"978-1-5090-4257-9","author":[{"family":"Sravani","given":"K."},{"family":"Pavithra","given":"D"},{"family":"Dhanya","given":"S."},{"family":"Thirumalai","given":"Chandrasegar"}],"issued":{"date-parts":[["2017",5]]},"accessed":{"date-parts":[["2020",1,13]]}}}],"schema":"https://github.com/citation-style-language/schema/raw/master/csl-citation.json"} (Sravani et al., 2017). So if the locations in memory are not available, then array can't be formed. A linked list is further divided into its types like a singly linked list, which is a dimensional and doubly linked list, which is two dimensional. Some more variations of a linked list are also present, like the circular linked list where the last node references the first node.

Stack and queue are two major types of arrangement of data that can be executed using a linked list. Two major operations that are performed on a linked list are push and pop. Push means to add an element/object in a particular location on a linked list. While the pop operations involve taking the object out of a particular location in a linked list. Stack works on the principle of Last In First Out (LIFO) ADDIN ZOTERO_ITEM CSL_CITATION {"citationID":"HVRGRhAS","properties":{"formattedCitation":"(Dale et al., 2016)","plainCitation":"(Dale et al., 2016)","noteIndex":0},"citationItems":[{"id":40,"uris":["http://zotero.org/users/local/WKtM8IGm/items/RISLTQMF"],"uri":["http://zotero.org/users/local/WKtM8IGm/items/RISLTQMF"],"itemData":{"id":40,"type":"book","title":"Object-Oriented Data Structures Using Java","publisher":"Jones & Bartlett Publishers","number-of-pages":"714","source":"Google Books","abstract":"The updated and revised Object-Oriented Data Structures Using Java, Fourth Edition is an essential resource for students learning data structures using the Java programming language. It presents both the traditional and modern data structure topics with an emphasis on problem-solving and object-oriented software design. Beginning early and continuing throughout the text, it introduces and expands upon the use of many Java features such as classes, objects, generics, polymorphism, packages, interfaces, library classes, inheritance, exceptions, and threads.","ISBN":"978-1-284-08909-7","note":"Google-Books-ID: LSbtDAAAQBAJ","language":"en","author":[{"family":"Dale","given":""},{"family":"Joyce","given":"Daniel T."},{"family":"Weems","given":"Chip"}],"issued":{"date-parts":[["2016",9]]}}}],"schema":"https://github.com/citation-style-language/schema/raw/master/csl-citation.json"} (Dale et al., 2016). To implement a stack, push the objects at the head location and also pop from the head location, or you can add objects at the tail location and pop from the tail location as well. The queue is based on the First In First Out (FIFO) rule. To implement a queue, add nodes at the tail and pop from the head ADDIN ZOTERO_ITEM CSL_CITATION {"citationID":"qiFAf7Kh","properties":{"formattedCitation":"(Liu et al., 2017)","plainCitation":"(Liu et al., 2017)","noteIndex":0},"citationItems":[{"id":43,"uris":["http://zotero.org/users/local/WKtM8IGm/items/5VZG9QMN"],"uri":["http://zotero.org/users/local/WKtM8IGm/items/5VZG9QMN"],"itemData":{"id":43,"type":"paper-conference","title":"Concurrent Data Structures for Near-Memory Computing","container-title":"Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA '17","publisher":"ACM Press","publisher-place":"Washington, DC, USA","page":"235-245","source":"DOI.org (Crossref)","event":"the 29th ACM Symposium","event-place":"Washington, DC, USA","URL":"http://dl.acm.org/citation.cfm?doid=3087556.3087582","DOI":"10.1145/3087556.3087582","ISBN":"978-1-4503-4593-4","language":"en","author":[{"family":"Liu","given":"Zhiyu"},{"family":"Calciu","given":"Irina"},{"family":"Herlihy","given":"Maurice"},{"family":"Mutlu","given":"Onur"}],"issued":{"date-parts":[["2017"]]},"accessed":{"date-parts":[["2020",1,13]]}}}],"schema":"https://github.com/citation-style-language/schema/raw/master/csl-citation.json"} (Liu et al., 2017).

In terms of preference for the usage of either stack or queue, it all depends upon the situation. There is no single preferred method e.g if something needs to be implemented where the FIFO method is to be used then queues are the best way. While any implementation that requires LIFO, stack would be used.

When talking about stacks, one real-life example would be that of a garage of small width so that one car may enter at a time. You put all your cars in the garage one by one. If you have to remove the first car you put in, you would have to remove all the other cars that you inserted after that particular one. Also, placing plates in a box is an example of the stack. You have to take out all the plates before you take the first one out.

When discussing about the queue, the shopping malls are the perfect example. You go shopping for groceries, and you make a queue at the checkout. If you are the first in line, you would be the first to check out.

References

ADDIN ZOTERO_BIBL {"uncited":[],"omitted":[],"custom":[]} CSL_BIBLIOGRAPHY Dale, Joyce, D. T., & Weems, C. (2016). Object-Oriented Data Structures Using Java. Jones & Bartlett Publishers.

Liu, Z., Calciu, I., Herlihy, M., & Mutlu, O. (2017). Concurrent Data Structures for Near-Memory Computing. Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures - SPAA ’17, 235–245. https://doi.org/10.1145/3087556.3087582

Sravani, K., Pavithra, D., Dhanya, S., & Thirumalai, C. (2017). Analyzing the linked list complexity using correlation methods. 2017 International Conference on Trends in Electronics and Informatics (ICEI), 1127–1130. https://doi.org/10.1109/ICOEI.2017.8300888