• Julian's Globe

    LINKED LIST

    Let us begin with defining the two words of this data structure. We will first analyze the word "list" and how it relates within the context of computer science. As defined by the Merriam-Webster dictionary, a basic definition of list is "a simple series of words or numerals (such as the names of persons or objects)." For example, a grocery list where we there is a series of items such as milk, bread, chips, cookies, and eggs, or a guest list for a family birthday party which includes names such as Juan, Andrew, Emily, Carl. Now we will analyze the word "linked" and how it relates within the context of computer science. The verb link means to join two or more objects by some form. Therefore, a linked list may be described as two or more lists linked together such as in the image below:


    Moving on from this real life example, we will begin to generalize this idea of linked lists such that they can contain any sort of data you could possibly imagine. It is up to you to decide what data each list will contain. However, as a rule of thumb it is generally better to have each list in a linkage of lists pertain to the same type of data as all the other lists. Looking at the examples above with the linked grocery lists, only grocery lists should to be allowed where including a laundry list or a list of birthday party guests would be inappropriate. The reason for this is that data can get messy, and it is much neater to contain one data type within a single data structure at a time. In computer science, each individual list is generally referred to as a node. A node may be defined as a specific data containing element with references to adjacent nodes. It is easy to visually depict a linkage between two nodes, but a computer cannot easily visually depict this. Therefore each node must contain within itself a data entry pertaining to adjacent nodes. At this point, we reach the difference between a singly-linked list and a doubly-linked list in which the two differ by which data entries it contains for adjacent nodes.

    Singly-Linked Lists

    Singly-Linked lists are a special form of a linked-list such that each node contains a data entry for its succeeding node but not for its previous node.

    Doubly-Linked Lists

    Doubly-Linked lists are a special form of a linked-list such that each node contains a data entry for both its succeeding node and its previous node.