# trekhleb/javascript-algorithms

Latest commit e954d6d Apr 16, 2019
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
__test__ Sep 8, 2018

Read this in other languages: 简体中文, Русский, 日本語, Português

In computer science, a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality as compared to linked lists.

## Pseudocode for Basic Operations

### Insert

``````Add(value)
Pre: value is the value to add to the list
Post: value has been placed at the tail of the list
n ← node(value)
tail ← n
else
tail.next ← n
tail ← n
end if
``````
``````Prepend(value)
Pre: value is the value to add to the list
Post: value has been placed at the head of the list
n ← node(value)
if tail = ø
tail ← n
end
end Prepend
``````

### Search

``````Contains(head, value)
value is the value to search for
Post: the item is either in the linked list, true; otherwise false
while n != ø and n.value != value
n ← n.next
end while
if n = ø
return false
end if
return true
end Contains
``````

### Delete

``````Remove(head, value)
value is the value to remove from the list
Post: value is removed from the list, true, otherwise false
return false
end if
if n.value = value
tail ← ø
else
end if
return true
end if
while n.next != ø and n.next.value != value
n ← n.next
end while
if n.next != ø
if n.next = tail
tail ← n
end if
n.next ← n.next.next
return true
end if
return false
end Remove
``````

### Traverse

``````Traverse(head)
Post: the items in the list have been traversed
while n != ø
yield n.value
n ← n.next
end while
end Traverse
``````

### Traverse in Reverse

``````ReverseTraversal(head, tail)
Pre: head and tail belong to the same list
Post: the items in the list have been traversed in reverse order
if tail != ø
curr ← tail
while prev.next != curr
prev ← prev.next
end while
yield curr.value
curr ← prev
end while
yield curr.value
end if
end ReverseTraversal
``````

## Complexities

### Time Complexity

Access Search Insertion Deletion
O(n) O(n) O(1) O(n)

O(n)

## References

You can’t perform that action at this time.