Doubly-linked list/Definition: Difference between revisions
Example usage of Python built-in and an alternative Python implementation
(Added Wren) |
(Example usage of Python built-in and an alternative Python implementation) |
||
Line 2,609:
=={{header|Python}}==
In the high level language Python, its <code>list</code> native datatype should be used. It automatically preserves the integrity of the list w.r.t. loops and allows insertion at any point using [http://docs.python.org/library/stdtypes.html#typesseq-mutable list.insert()] via an integer index into the list rather than a machine-code level pointer to a list element.
===collections.deque===
If, as you would expect from a doubly-linked list, you need to efficiently
append items to the start of an ordered collection, use Python’s built-in
[https://docs.python.org/3/library/collections.html#collections.deque collections.deque]
datatype. See [https://wiki.python.org/moin/TimeComplexity TimeComplexity].
<lang python>
from collections import deque
some_list = deque(["a", "b", "c"])
print(some_list)
some_list.appendleft("Z")
print(some_list)
for value in reversed(some_list):
print(value)
</lang>
{{out}}
<pre>
$ python deque_example.py
deque(['a', 'b', 'c'])
deque(['Z', 'a', 'b', 'c'])
c
b
a
Z
</pre>
===Alternative===
Although a <code>deque</code> is preferable in most cases, this implementation gives you the
option to access nodes and slice "views" from a <code>DoublyLinkedList</code>. Things that
<code>collections.deque</code> does not do.
Retrieving an item by it’s index returns the node’s value. Similarly, iterating
a <code>DoublyLinkedList</code> yields a sequence of values, not a sequence of nodes. The
return value of a slice is a <code>DoublyLinkedListView</code>, which shares common nodes with
the original list.
Note that, without a concrete use case, the decision as to which of the special
methods should return a node’s value or a <code>DoublyLinkedListView</code> is somewhat
arbitrary. One might also choose to do away with <code>DoublyLinkedListView</code> and return
a new <code>DoublyLinkedList</code>, accepting that update operations on a derived list could
break links between nodes in other lists.
<lang python>
"""A doubly-linked list. Requires Python >=3.7"""
from __future__ import annotations
import math
from abc import ABC
from collections.abc import MutableSequence
from collections.abc import Sequence
from dataclasses import dataclass
from dataclasses import field
from typing import Any
from typing import Iterable
from typing import Iterator
from typing import Optional
from typing import Union
@dataclass
class Node:
value: Any
prev: Optional[Node] = field(default=None)
next: Optional[Node] = field(default=None)
class BaseDoublyLinkedList(ABC):
def __len__(self):
return self.size
def __iter__(self) -> Iterator[Any]:
node = self.head
cnt = 1
while node is not None and cnt <= self.size:
yield node.value
node = node.next
cnt += 1
def __reversed__(self) -> Iterator[Any]:
node = self.tail
while node is not None:
yield node.value
node = node.prev
def __getitem__(self, key: Union[int, slice]) -> Optional[Any]:
if isinstance(key, int):
node = self._find_node(key)
return node.value
if key.step not in (None, 1):
raise IndexError("can't step more than 1")
start = key.start or 0
node = self._find_node(start)
return DoublyLinkedListView(node, key.stop - start - 1)
def _find_node(self, index) -> Node:
if index > self.size - 1 or index < -self.size:
raise IndexError("list index out of range")
if index >= 0:
node = self.head
for _ in range(index):
node = node.next
else:
node = self.tail
for _ in range(self.size - 1, self.size - abs(index), -1):
node = node.prev
return node
class DoublyLinkedListView(BaseDoublyLinkedList, Sequence):
def __init__(self, node, stop=math.inf):
self.head = node
# Find the tail
cnt = 1
while node is not None and cnt <= stop:
node = node.next
cnt += 1
self.tail = node
self.size = cnt
def __repr__(self):
return f"DoublyLinkedListView([{', '.join(repr(v) for v in self)}])"
def __str__(self):
return repr(self)
class DoublyLinkedList(BaseDoublyLinkedList, MutableSequence):
def __init__(self, iterable: Iterable):
it = iter(iterable)
# Possibly empty iterable
try:
self.head = Node(value=next(it))
self.tail = self.head
self.size = 1
except StopIteration:
self.head = None
self.tail = None
self.size = 0
node = self.head
for val in it:
self.tail = Node(value=val, prev=node)
node.next = self.tail
node = self.tail
self.size += 1
def __repr__(self):
return f"DoublyLinkedList([{', '.join(repr(v) for v in self)}])"
def __str__(self):
return repr(self)
def __setitem__(self, key, value):
node = self._find_node(key)
node.value = value
def __delitem__(self, key) -> None:
node = self._find_node(key)
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
def _find_node(self, index) -> Node:
if index > self.size - 1 or index < -self.size:
raise IndexError("list index out of range")
if index >= 0:
node = self.head
for _ in range(index):
node = node.next
else:
node = self.tail
for _ in range(self.size - 1, self.size - abs(index), -1):
node = node.prev
return node
def insert(self, index: int, value: Any) -> None:
node = self._find_node(index)
new_node = Node(value=value, prev=node.prev, next=node)
node.prev.next = new_node
node.prev = node
self.size += 1
def append(self, value: Any) -> None:
tail = self.tail
node = Node(value=value, prev=tail)
tail.next = node
self.tail = node
self.size += 1
def appendleft(self, value: Any) -> None:
head = self.head
node = Node(value=value, next=head)
head.prev = node
self.head = node
self.size += 1
def pop(self) -> Any:
value = self.tail.value
self.tail = self.tail.prev
self.tail.next = None
self.size -= 1
return value
def popleft(self) -> Any:
value = self.head.value
self.head = self.head.next
self.head.prev = None
self.size -= 1
return value
</lang>
=={{header|Racket}}==
| |||