Linked list: Difference between revisions
Content added Content deleted
m (Added wikipedia-style bolding and data structures link) |
m (Complexity of list operations mentioned) |
||
| Line 5: | Line 5: | ||
==Singly-Linked List== |
==Singly-Linked List== |
||
A singly-linked list allows traversal in one direction, forward. To this end, each data element contains a reference to the next data element in the sequence. |
A singly-linked list allows traversal in one direction, forward. To this end, each data element contains a reference to the next data element in the sequence. Single-linked list has [[O]](1) insertion time and [[O]](n) removal time. |
||
===See also=== |
===See also=== |
||
| Line 16: | Line 16: | ||
==Doubly-Linked List== |
==Doubly-Linked List== |
||
A doubly-linked list allows traversal in two directions, forward and back. To this end, each data element contains references to both the previous and next elements. |
A doubly-linked list allows traversal in two directions, forward and back. To this end, each data element contains references to both the previous and next elements. Doubly-linked list has [[O]](1) removal and insertion times. Further, these operations do not require the list head. |
||
===See also=== |
===See also=== |
||