Category: 

What Is a Linked Data Structure?

Article Details
  • Written By: Eugene P.
  • Edited By: Angela B.
  • Last Modified Date: 22 August 2016
  • Copyright Protected:
    2003-2016
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
In late 19th-century London, mail was delivered to residential addresses up to twelve times each day.   more...

September 28 ,  1924 :  Two US military planes complete the first flights around the world.  more...

A linked data structure is a collection of‭ ‬data arranged in a list-like format.‭ ‬Each piece of datum in the list is referred to as a node.‭ ‬Each node is connected to the next‭ ‬one on the list by a reference to the memory address of that‭ ‬subsequent‭ ‬node.‭ ‬Linked data structures are used in place of an array when the number of nodes on a list is unknown or‭ ‬might grow or shrink over the course of the execution of the program.‭ ‬The most common‭ ‬type of linked data structure is called a linked list.

A node of a linked data structure generally contains two pieces of information — a reference to the actual data being stored and a reference to the next node on the list.‭ ‬A linked list is traversed,‭ ‬or searched,‭ ‬by stepping through each of the data nodes, beginning at the first one,‭ or the head of the list.‭ ‬There is no way to find information in a linked list without sequentially moving through the nodes from beginning to end.

Most linked data structures‭ ‬will use as little memory as‭ ‬possible during program execution.‭ ‬If a linked list is created with only one node‭ ‬and no other nodes are added,‭ ‬that list will‭ ‬take up the memory required for‭ ‬only‭ ‬one node.‭ ‬This is in stark contrast to an array‭ ‬data‭ ‬structure in which the size of the entire array must be declared and allocated at the start of the program and cannot be changed.

Ad

Linked lists‭ ‬pay for their efficient use of memory resources by requiring more computing power.‭ ‬Finding a specific piece of data in a linked list requires looping through the entire list every time,‭ ‬so it can be slower to access information in the middle of the list.‭ ‬Removing or reordering data in a linked list also can be more computationally intensive than managing an array in which elements can be‭ ‬swapped ‬easily.

A linked data structure is not required to have only one reference to the next node; ‬it can have several.‭ ‬Some linked lists have two node references, ‬one to the next node in the list and one to the previous node.‭ ‬These are known as doubly linked lists.‭ ‬This can make moving through a list in either direction much faster, though at the expense of increased memory usage for the data structure.

It is possible for linked lists‭ ‬to have three or more references to other nodes in the list.‭ ‬This creates a structure similar to a tree with entire branches of nodes spawning from a single‭ ‬one.‭ ‬These types of data structures are called multiply linked lists.‭ ‬Multiply linked lists are particularly useful for complex sorting algorithms that are used to structure data.‭ ‬Search trees are‭ ‬possible‭ ‬largely‭ ‬because of the use of linked‭ ‬data structures‭ ‬to create multiple,‭ ‬variable-length branches.

Ad

You might also Like

Recommended

Discuss this Article

Post your comments

exception 'Exception' with message 'error writing captcha: Duplicate entry '2147483647' for key 'PRIMARY'' in /ssd/www/wisegeek/public_html/_core/classes/public/Captcha.php:44
Stack trace:
#0 /ssd/www/wisegeek/public_html/_core/controls/public/ControlDiscussionPostBox.php(324): Captcha->createCaptcha()
#1 /ssd/www/wisegeek/public_html/framework/classes/Control.php(104): ControlDiscussionPostBox->preRender(false)
#2 /ssd/www/wisegeek/public_html/framework/classes/Control.php(149): Control->render()
#3 /ssd/www/wisegeek/public_html/tpl/default-nocustom-lu/pages/public/article/article.htm(526): Control->__toString()
#4 /ssd/www/wisegeek/public_html/framework/classes/Control.php(300): require('/ssd/www/wisege...')
#5 /ssd/www/wisegeek/public_html/framework/classes/Control.php(309): Control->requireTpl('pages/public/ar...', Object(PageArticleCom), true)
#6 /ssd/www/wisegeek/public_html/framework/classes/Control.php(131): Control->renderTpl('pages/public/ar...', Object(PageArticleCom))
#7 /ssd/www/wisegeek/public_html/framework/classes/FormDataControl.php(87): Control->renderTemplate()
#8 /ssd/www/wisegeek/public_html/framework/classes/Control.php(109): FormDataControl->renderTemplate()
#9 /ssd/www/wisegeek/public_html/framework/classes/ScriptPage.php(50): Control->render(false)
#10 /ssd/www/wisegeek/public_html/framework/classes/Control.php(149): ScriptPage->render()
#11 /ssd/www/wisegeek/public_html/framework/classes/Page.php(97): Control->__toString()
#12 /ssd/www/wisegeek/public_html/_core/classes/public/PublicFrontController.php(443): Page->processRequest()
#13 /ssd/www/wisegeek/public_html/_core/classes/public/PublicFrontController.php(7): PublicFrontController->renderPage()
#14 /ssd/www/wisegeek/public_html/index.php(11): PublicFrontController::run()
#15 {main}