Coverage for pyTooling / LinkedList / __init__.py: 89%

1# ==================================================================================================================== # 

2# _____ _ _ _ _ _ _ _ _ _ # 

3# _ __ _ |_ _|__ ___ | (_)_ __ __ _ | | (_)_ __ | | _____ __| | | (_)___| |_ # 

4# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` | | | | | '_ \| |/ / _ \/ _` | | | / __| __| # 

5# | |_) | |_| || | (_) | (_) | | | | | | (_| |_| |___| | | | | < __/ (_| | |___| \__ \ |_ # 

6# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)_____|_|_| |_|_|\_\___|\__,_|_____|_|___/\__| # 

7# |_| |___/ |___/ # 

8# ==================================================================================================================== # 

9# Authors: # 

10# Patrick Lehmann # 

11# # 

12# License: # 

13# ==================================================================================================================== # 

14# Copyright 2025-2026 Patrick Lehmann - Bötzingen, Germany # 

15# # 

16# Licensed under the Apache License, Version 2.0 (the "License"); # 

17# you may not use this file except in compliance with the License. # 

18# You may obtain a copy of the License at # 

19# # 

20# http://www.apache.org/licenses/LICENSE-2.0 # 

21# # 

22# Unless required by applicable law or agreed to in writing, software # 

23# distributed under the License is distributed on an "AS IS" BASIS, # 

24# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # 

25# See the License for the specific language governing permissions and # 

26# limitations under the License. # 

27# # 

28# SPDX-License-Identifier: Apache-2.0 # 

29# ==================================================================================================================== # 

30# 

31"""An object-oriented doubly linked-list data structure for Python.""" 

32 

33from collections.abc import Sized 

34from typing import Generic, TypeVar, Optional as Nullable, Callable, Iterable, Generator, Tuple, List, Any 

35 

36from pyTooling.Decorators import readonly, export 

37from pyTooling.Exceptions import ToolingException 

38from pyTooling.MetaClasses import ExtendedType 

39from pyTooling.Common import getFullyQualifiedName 

40 

41 

42_NodeKey = TypeVar("_NodeKey") 

43_NodeValue = TypeVar("_NodeValue") 

44 

45 

46@export 

47class LinkedListException(ToolingException): 

48 """Base-exception of all exceptions raised by :mod:`pyTooling.LinkedList`.""" 

49 

50 

51@export 

52class Node(Generic[_NodeKey, _NodeValue], metaclass=ExtendedType, slots=True): 

53 """ 

54 The node in an object-oriented doubly linked-list. 

55 

56 It contains a reference to the doubly linked list (:attr:`_list`), the previous node (:attr:`_previous`), the next 

57 node (:attr:`_next`) and the data (:attr:`_value`). Optionally, a key (:attr:`_key`) can be stored for sorting 

58 purposes. 

59 

60 The :attr:`_previous` field of the **first node** in a doubly linked list is ``None``. Similarly, the :attr:`_next` 

61 field of the **last node** is ``None``. ``None`` represents the end of the linked list when iterating it node-by-node. 

62 """ 

63 

64 _linkedList: Nullable["LinkedList[_NodeValue]"] #: Reference to the doubly linked list instance. 

65 _previousNode: Nullable["Node[_NodeKey, _NodeValue]"] #: Reference to the previous node. 

66 _nextNode: Nullable["Node[_NodeKey, _NodeValue]"] #: Reference to the next node. 

67 _key: Nullable[_NodeKey] #: The sortable key of the node. 

68 _value: _NodeValue #: The value of the node. 

69 

70 def __init__( 

71 self, 

72 value: _NodeValue, 

73 key: Nullable[_NodeKey] = None, 

74 previousNode: Nullable["Node[_NodeKey, _NodeValue]"] = None, 

75 nextNode: Nullable["Node[_NodeKey, _NodeValue]"] = None 

76 ) -> None: 

77 """ 

78 Initialize a linked list node. 

79 

80 :param value: Value to store in the node. 

81 :param key: Optional sortable key to store in the node. 

82 :param previousNode: Optional reference to the previous node. 

83 :param nextNode: Optional reference to the next node. 

84 :raises TypeError: If parameter 'previous' is not of type :class:`Node`. 

85 :raises TypeError: If parameter 'next' is not of type :class:`Node`. 

86 """ 

87 self._previousNode = previousNode 

88 self._nextNode = nextNode 

89 self._value = value 

90 self._key = value 

91 

92 # Attache to previous node 

93 if previousNode is not None: 

94 if not isinstance(previousNode, Node): 

95 ex = TypeError(f"Parameter 'previous' is not of type Node.") 

96 ex.add_note(f"Got type '{getFullyQualifiedName(previousNode)}'.") 

97 raise ex 

98 

99 # PreviousNode is part of a list 

100 if previousNode._linkedList is not None: 100 ↛ 101line 100 didn't jump to line 101 because the condition on line 100 was never true

101 self._linkedList = previousNode._linkedList 

102 self._linkedList._count += 1 

103 

104 # Check if previous was the last node 

105 if previousNode._nextNode is None: 

106 self._nextNode = None 

107 self._linkedList._lastNode = self 

108 else: 

109 self._nextNode = previousNode._nextNode 

110 self._nextNode._previousNode = self 

111 else: 

112 self._linkedList = None 

113 

114 previousNode._nextNode = self 

115 

116 if nextNode is not None: 116 ↛ 117line 116 didn't jump to line 117 because the condition on line 116 was never true

117 if not isinstance(nextNode, Node): 

118 ex = TypeError(f"Parameter 'next' is not of type Node.") 

119 ex.add_note(f"Got type '{getFullyQualifiedName(nextNode)}'.") 

120 raise ex 

121 

122 if nextNode._linkedList is not None: 

123 if self._linkedList is not None: 

124 if self._linkedList is not previousNode._linkedList: 

125 raise ValueError() 

126 

127 previousNode._nextNode = self 

128 elif nextNode is not None: 

129 if not isinstance(nextNode, Node): 

130 ex = TypeError(f"Parameter 'next' is not of type Node.") 

131 ex.add_note(f"Got type '{getFullyQualifiedName(nextNode)}'.") 

132 raise ex 

133 

134 # NextNode is part of a list 

135 if nextNode._linkedList is not None: 135 ↛ 136line 135 didn't jump to line 136 because the condition on line 135 was never true

136 self._linkedList = nextNode._linkedList 

137 self._linkedList._count += 1 

138 

139 # Check if next was the first node 

140 if nextNode._previousNode is None: 

141 self._previousNode = None 

142 self._linkedList._firstNode = self 

143 else: 

144 self._previousNode = nextNode._previousNode 

145 self._previousNode._nextNode = self 

146 else: 

147 self._linkedList = None 

148 

149 nextNode._previousNode = self 

150 else: 

151 self._linkedList = None 

152 

153 @readonly 

154 def List(self) -> Nullable["LinkedList[_NodeValue]"]: 

155 """ 

156 Read-only property to access the linked list, this node belongs to. 

157 

158 :return: The linked list, this node is part of, or ``None``. 

159 """ 

160 return self._linkedList 

161 

162 @readonly 

163 def PreviousNode(self) -> Nullable["Node[_NodeKey, _NodeValue]"]: 

164 """ 

165 Read-only property to access node's predecessor. 

166 

167 This reference is ``None`` if the node is the first node in the doubly linked list. 

168 

169 :return: The node before the current node or ``None``. 

170 """ 

171 return self._previousNode 

172 

173 @readonly 

174 def NextNode(self) -> Nullable["Node[_NodeKey, _NodeValue]"]: 

175 """ 

176 Read-only property to access node's successor. 

177 

178 This reference is ``None`` if the node is the last node in the doubly linked list. 

179 

180 :return: The node after the current node or ``None``. 

181 """ 

182 return self._nextNode 

183 

184 @property 

185 def Key(self) -> _NodeKey: 

186 """ 

187 Property to access the node's internal key. 

188 

189 The key can be a scalar or a reference to an object. 

190 

191 :return: The node's key. 

192 """ 

193 return self._key 

194 

195 @Key.setter 

196 def Key(self, key: _NodeKey) -> None: 

197 self._key = key 

198 

199 @property 

200 def Value(self) -> _NodeValue: 

201 """ 

202 Property to access the node's internal data. 

203 

204 The data can be a scalar or a reference to an object. 

205 

206 :return: The node's value. 

207 """ 

208 return self._value 

209 

210 @Value.setter 

211 def Value(self, value: _NodeValue) -> None: 

212 self._value = value 

213 

214 def InsertNodeBefore(self, node: "Node[_NodeKey, _NodeValue]") -> None: 

215 """ 

216 Insert a node before this node. 

217 

218 :param node: Node to insert. 

219 :raises ValueError: If parameter 'node' is ``None``. 

220 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

221 :raises LinkedListException: If parameter 'node' is already part of another linked list. 

222 """ 

223 if node is None: 

224 raise ValueError(f"Parameter 'node' is None.") 

225 

226 if not isinstance(node, Node): 

227 ex = TypeError(f"Parameter 'node' is not of type Node.") 

228 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.") 

229 raise ex 

230 

231 if node._linkedList is not None: 

232 raise LinkedListException(f"Parameter 'node' belongs to another linked list.") 

233 

234 node._linkedList = self._linkedList 

235 node._nextNode = self 

236 node._previousNode = self._previousNode 

237 if self._previousNode is None: 

238 self._linkedList._firstNode = node 

239 else: 

240 self._previousNode._nextNode = node 

241 self._previousNode = node 

242 self._linkedList._count += 1 

243 

244 def InsertNodeAfter(self, node: "Node[_NodeKey, _NodeValue]") -> None: 

245 """ 

246 Insert a node after this node. 

247 

248 :param node: Node to insert. 

249 :raises ValueError: If parameter 'node' is ``None``. 

250 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

251 :raises LinkedListException: If parameter 'node' is already part of another linked list. 

252 """ 

253 if node is None: 

254 raise ValueError(f"Parameter 'node' is None.") 

255 

256 if not isinstance(node, Node): 

257 ex = TypeError(f"Parameter 'node' is not of type Node.") 

258 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.") 

259 raise ex 

260 

261 if node._linkedList is not None: 

262 raise LinkedListException(f"Parameter 'node' belongs to another linked list.") 

263 

264 node._linkedList = self._linkedList 

265 node._previousNode = self 

266 node._nextNode = self._nextNode 

267 if self._nextNode is None: 

268 self._linkedList._lastNode = node 

269 else: 

270 self._nextNode._previousNode = node 

271 self._nextNode = node 

272 self._linkedList._count += 1 

273 

274 # move forward 

275 # move backward 

276 # move by relative pos 

277 # move to position 

278 # move to begin 

279 # move to end 

280 

281 # insert tuple/list/linkedlist before 

282 # insert tuple/list/linkedlist after 

283 

284 # iterate forward for n 

285 # iterate backward for n 

286 

287 # slice to tuple / list starting from that node 

288 

289 # swap left by n 

290 # swap right by n 

291 

292 def Remove(self) -> _NodeValue: 

293 """ 

294 Remove this node from the linked list. 

295 """ 

296 if self._previousNode is None: 

297 if self._linkedList is not None: 297 ↛ 306line 297 didn't jump to line 306 because the condition on line 297 was always true

298 self._linkedList._firstNode = self._nextNode 

299 self._linkedList._count -= 1 

300 

301 if self._nextNode is None: 

302 self._linkedList._lastNode = None 

303 

304 self._linkedList = None 

305 

306 if self._nextNode is not None: 

307 self._nextNode._previousNode = None 

308 

309 self._nextNode = None 

310 elif self._nextNode is None: 

311 if self._linkedList is not None: 311 ↛ 316line 311 didn't jump to line 316 because the condition on line 311 was always true

312 self._linkedList._lastNode = self._previousNode 

313 self._linkedList._count -= 1 

314 self._linkedList = None 

315 

316 self._previousNode._nextNode = None 

317 self._previousNode = None 

318 else: 

319 self._previousNode._nextNode = self._nextNode 

320 self._nextNode._previousNode = self._previousNode 

321 self._nextNode = None 

322 self._previousNode = None 

323 

324 if self._linkedList is not None: 324 ↛ 328line 324 didn't jump to line 328 because the condition on line 324 was always true

325 self._linkedList._count -= 1 

326 self._linkedList = None 

327 

328 return self._value 

329 

330 def IterateToFirst(self, includeSelf: bool = False) -> Generator["Node[_NodeKey, _NodeValue]", None, None]: 

331 """ 

332 Return a generator iterating backward from this node to the list's first node. 

333 

334 Optionally, this node can be included into the generated sequence. 

335 

336 :param includeSelf: If ``True``, include this node into the sequence, otherwise start at previous node. 

337 :return: A sequence of nodes towards the list's first node. 

338 """ 

339 previousNode = self._previousNode 

340 

341 if includeSelf: 

342 yield self 

343 

344 node = previousNode 

345 while node is not None: 

346 previousNode = node._previousNode 

347 yield node 

348 node = previousNode 

349 

350 def IterateToLast(self, includeSelf: bool = False) -> Generator["Node[_NodeKey, _NodeValue]", None, None]: 

351 """ 

352 Return a generator iterating forward from this node to the list's last node. 

353 

354 Optionally, this node can be included into the generated sequence by setting. 

355 

356 :param includeSelf: If ``True``, include this node into the sequence, otherwise start at next node. 

357 :return: A sequence of nodes towards the list's last node. 

358 """ 

359 nextNode = self._nextNode 

360 

361 if includeSelf: 

362 yield self 

363 

364 node = nextNode 

365 while node is not None: 

366 nextNode = node._nextNode 

367 yield node 

368 node = nextNode 

369 

370 def __repr__(self) -> str: 

371 return f"Node: {self._value}" 

372 

373 

374@export 

375class LinkedList(Generic[_NodeKey, _NodeValue], metaclass=ExtendedType, slots=True): 

376 """An object-oriented doubly linked-list.""" 

377 

378 _firstNode: Nullable[Node[_NodeKey, _NodeValue]] #: Reference to the first node of the linked list. 

379 _lastNode: Nullable[Node[_NodeKey, _NodeValue]] #: Reference to the last node of the linked list. 

380 _count: int #: Number of nodes in the linked list. 

381 

382 # allow iterable to initialize the list 

383 def __init__(self, nodes: Nullable[Iterable[Node[_NodeKey, _NodeValue]]] = None) -> None: 

384 """ 

385 Initialize an empty linked list. 

386 

387 Optionally, an iterable can be given to initialize the linked list. The order is preserved. 

388 

389 :param nodes: Optional iterable to initialize the linked list. 

390 :raises TypeError: If parameter 'nodes' is not an :class:`iterable <typing.Iterable>`. 

391 :raises TypeError: If parameter 'nodes' items are not of type :class:`Node`. 

392 :raises LinkedListException: If parameter 'nodes' contains items which are already part of another linked list. 

393 """ 

394 if nodes is None: 

395 self._firstNode = None 

396 self._lastNode = None 

397 self._count = 0 

398 elif not isinstance(nodes, Iterable): 

399 ex = TypeError(f"Parameter 'nodes' is not an iterable.") 

400 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.") 

401 raise ex 

402 else: 

403 if isinstance(nodes, Sized) and len(nodes) == 0: 

404 self._firstNode = None 

405 self._lastNode = None 

406 self._count = 0 

407 return 

408 

409 try: 

410 first = next(iterator := iter(nodes)) 

411 except StopIteration: 

412 self._firstNode = None 

413 self._lastNode = None 

414 self._count = 0 

415 return 

416 

417 if not isinstance(first, Node): 

418 ex = TypeError(f"First element in parameter 'nodes' is not of type Node.") 

419 ex.add_note(f"Got type '{getFullyQualifiedName(first)}'.") 

420 raise ex 

421 elif first._linkedList is not None: 

422 raise LinkedListException(f"First element in parameter 'nodes' is assigned to different list.") 

423 

424 position = 1 

425 first._linkedList = self 

426 first._previousNode = None 

427 self._firstNode = previous = node = first 

428 

429 for node in iterator: 

430 if not isinstance(node, Node): 

431 ex = TypeError(f"{position}. element in parameter 'nodes' is not of type Node.") 

432 ex.add_note(f"Got type '{getFullyQualifiedName(node)}'.") 

433 raise ex 

434 elif node._linkedList is not None: 

435 raise LinkedListException(f"{position}. element in parameter 'nodes' is assigned to different list.") 

436 

437 node._linkedList = self 

438 node._previousNode = previous 

439 previous._nextNode = node 

440 

441 previous = node 

442 position += 1 

443 

444 self._lastNode = node 

445 self._count = position 

446 node._nextNode = None 

447 

448 @readonly 

449 def IsEmpty(self) -> int: 

450 """ 

451 Read-only property to access the number of . 

452 

453 This reference is ``None`` if the node is the last node in the doubly linked list. 

454 

455 :return: ``True`` if linked list is empty, otherwise ``False`` 

456 """ 

457 return self._count == 0 

458 

459 @readonly 

460 def Count(self) -> int: 

461 """ 

462 Read-only property to access the number of nodes in the linked list. 

463 

464 :return: Number of nodes. 

465 """ 

466 return self._count 

467 

468 @readonly 

469 def FirstNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]: 

470 """ 

471 Read-only property to access the first node in the linked list. 

472 

473 In case the list is empty, ``None`` is returned. 

474 

475 :return: First node. 

476 """ 

477 return self._firstNode 

478 

479 @readonly 

480 def LastNode(self) -> Nullable[Node[_NodeKey, _NodeValue]]: 

481 """ 

482 Read-only property to access the last node in the linked list. 

483 

484 In case the list is empty, ``None`` is returned. 

485 

486 :return: Last node. 

487 """ 

488 return self._lastNode 

489 

490 def Clear(self) -> None: 

491 """ 

492 Clear the linked list. 

493 """ 

494 self._firstNode = None 

495 self._lastNode = None 

496 self._count = 0 

497 

498 def InsertBeforeFirst(self, node: Node[_NodeKey, _NodeValue]) -> None: 

499 """ 

500 Insert a node before the first node. 

501 

502 :param node: Node to insert. 

503 :raises ValueError: If parameter 'node' is ``None``. 

504 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

505 :raises LinkedListException: If parameter 'node' is already part of another linked list. 

506 """ 

507 if node is None: 

508 raise ValueError(f"Parameter 'node' is None.") 

509 

510 if not isinstance(node, Node): 

511 ex = TypeError(f"Parameter 'node' is not of type Node.") 

512 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.") 

513 raise ex 

514 

515 if node._linkedList is not None: 

516 raise LinkedListException(f"Parameter 'node' belongs to another linked list.") 

517 

518 node._linkedList = self 

519 node._previousNode = None 

520 node._nextNode = self._firstNode 

521 if self._firstNode is None: 

522 self._lastNode = node 

523 else: 

524 self._firstNode._previousNode = node 

525 self._firstNode = node 

526 self._count += 1 

527 

528 def InsertAfterLast(self, node: Node[_NodeKey, _NodeValue]) -> None: 

529 """ 

530 Insert a node after the last node. 

531 

532 :param node: Node to insert. 

533 :raises ValueError: If parameter 'node' is ``None``. 

534 :raises TypeError: If parameter 'node' is not of type :class:`Node`. 

535 :raises LinkedListException: If parameter 'node' is already part of another linked list. 

536 """ 

537 if node is None: 

538 raise ValueError(f"Parameter 'node' is None.") 

539 

540 if not isinstance(node, Node): 

541 ex = TypeError(f"Parameter 'node' is not of type Node.") 

542 ex.add_note(f"Got type '{getFullyQualifiedName(next)}'.") 

543 raise ex 

544 

545 if node._linkedList is not None: 

546 raise LinkedListException(f"Parameter 'node' belongs to another linked list.") 

547 

548 node._linkedList = self 

549 node._nextNode = None 

550 node._previousNode = self._lastNode 

551 if self._lastNode is None: 

552 self._firstNode = node 

553 else: 

554 node._previousNode._nextNode = node 

555 self._lastNode = node 

556 self._count += 1 

557 

558 def RemoveFirst(self) -> Node[_NodeKey, _NodeValue]: 

559 """ 

560 Remove first node from linked list. 

561 

562 :return: First node. 

563 :raises LinkedListException: If linked list is empty. 

564 """ 

565 if self._firstNode is None: 

566 raise LinkedListException(f"Linked list is empty.") 

567 

568 node = self._firstNode 

569 self._firstNode = node._nextNode 

570 if self._firstNode is None: 

571 self._lastNode = None 

572 self._count = 0 

573 else: 

574 self._firstNode._previousNode = None 

575 self._count -= 1 

576 

577 node._linkedList = None 

578 node._nextNode = None 

579 return node 

580 

581 def RemoveLast(self) -> Node[_NodeKey, _NodeValue]: 

582 """ 

583 Remove last node from linked list. 

584 

585 :return: Last node. 

586 :raises LinkedListException: If linked list is empty. 

587 """ 

588 if self._lastNode is None: 

589 raise LinkedListException(f"Linked list is empty.") 

590 

591 node = self._lastNode 

592 self._lastNode = node._previousNode 

593 if self._lastNode is None: 

594 self._firstNode = None 

595 self._count = 0 

596 else: 

597 self._lastNode._nextNode = None 

598 self._count -= 1 

599 

600 node._linkedList = None 

601 node._previousNode = None 

602 return node 

603 

604 

605 def GetNodeByIndex(self, index: int) -> Node[_NodeKey, _NodeValue]: 

606 """ 

607 Access a node in the linked list by position. 

608 

609 :param index: Node position to access. 

610 :return: Node at the given position. 

611 :raises ValueError: If parameter 'position' is out of range. 

612 

613 .. note:: 

614 

615 The algorithm starts iterating nodes from the shorter end. 

616 """ 

617 if index == 0: 

618 if self._firstNode is None: 

619 ex = ValueError("Parameter 'position' is out of range.") 

620 ex.add_note(f"Linked list is empty.") 

621 raise ex 

622 

623 return self._firstNode 

624 elif index == self._count - 1: 

625 return self._lastNode 

626 elif index >= self._count: 

627 ex = ValueError("Parameter 'position' is out of range.") 

628 ex.add_note(f"Linked list has {self._count} elements. Requested index: {index}.") 

629 raise ex 

630 

631 if index < self._count / 2: 631 ↛ 643line 631 didn't jump to line 643 because the condition on line 631 was always true

632 pos = 1 

633 node = self._firstNode._nextNode 

634 while node is not None: 

635 if pos == index: 

636 return node 

637 

638 node = node._nextNode 

639 pos += 1 

640 else: # pragma: no cover 

641 raise LinkedListException(f"Node position not found.") 

642 else: 

643 pos = self._count - 2 

644 node = self._lastNode._previousNode 

645 while node is not None: 

646 if pos == index: 

647 return node 

648 

649 node = node._previousNode 

650 pos -= 1 

651 else: # pragma: no cover 

652 raise LinkedListException(f"Node position not found.") 

653 

654 def Search(self, predicate: Callable[[Node], bool], reverse: bool = False) -> Node[_NodeKey, _NodeValue]: 

655 if self._firstNode is None: 

656 raise LinkedListException(f"Linked list is empty.") 

657 

658 if not reverse: 

659 node = self._firstNode 

660 while node is not None: 

661 if predicate(node): 

662 break 

663 

664 node = node._nextNode 

665 else: 

666 raise LinkedListException(f"Node not found.") 

667 else: 

668 node = self._lastNode 

669 while node is not None: 

670 if predicate(node): 

671 break 

672 

673 node = node._previousNode 

674 else: 

675 raise LinkedListException(f"Node not found.") 

676 

677 return node 

678 

679 def Reverse(self) -> None: 

680 """ 

681 Reverse the order of nodes in the linked list. 

682 """ 

683 if self._firstNode is None or self._firstNode is self._lastNode: 

684 return 

685 

686 node = self._lastNode = self._firstNode 

687 

688 while node is not None: 

689 last = node 

690 node = last._nextNode 

691 last._nextNode = last._previousNode 

692 

693 last._previousNode = node 

694 self._firstNode = last 

695 

696 def Sort(self, key: Nullable[Callable[[Node[_NodeKey, _NodeValue]], Any]] = None, reverse: bool = False) -> None: 

697 """ 

698 Sort the linked list in ascending or descending order. 

699 

700 The sort operation is **stable**. 

701 

702 :param key: Optional function to access a user-defined key for sorting. 

703 :param reverse: Optional parameter, if ``True`` sort in descending order, otherwise in ascending order. 

704 

705 .. note:: 

706 

707 The linked list is converted to an array, which is sorted by quicksort using the builtin :meth:`~list.sort`. 

708 Afterward, the sorted array is used to reconstruct the linked list in requested order. 

709 """ 

710 if (self._firstNode is None) or (self._firstNode is self._lastNode): 

711 return 

712 

713 if key is None: 

714 key = lambda node: node._value 

715 

716 sequence = [n for n in self.IterateFromFirst()] 

717 sequence.sort(key=key, reverse=reverse) 

718 

719 first = sequence[0] 

720 

721 position = 1 

722 first._previousNode = None 

723 self._firstNode = previous = node = first 

724 

725 for node in sequence[1:]: 

726 node._previousNode = previous 

727 previous._nextNode = node 

728 

729 previous = node 

730 position += 1 

731 

732 self._lastNode = node 

733 self._count = position 

734 node._nextNode = None 

735 

736 def IterateFromFirst(self) -> Generator[Node[_NodeKey, _NodeValue], None, None]: 

737 """ 

738 Return a generator iterating forward from list's first node to list's last node. 

739 

740 :return: A sequence of nodes towards the list's last node. 

741 """ 

742 if self._firstNode is None: 

743 return 

744 

745 node = self._firstNode 

746 while node is not None: 

747 nextNode = node._nextNode 

748 yield node 

749 node = nextNode 

750 

751 def IterateFromLast(self) -> Generator[Node[_NodeKey, _NodeValue], None, None]: 

752 """ 

753 Return a generator iterating backward from list's last node to list's first node. 

754 

755 :return: A sequence of nodes towards the list's first node. 

756 """ 

757 if self._lastNode is None: 

758 return 

759 

760 node = self._lastNode 

761 while node is not None: 

762 previousNode = node._previousNode 

763 yield node 

764 node = previousNode 

765 

766 def ToList(self, reverse: bool = False) -> List[Node[_NodeKey, _NodeValue]]: 

767 """ 

768 Convert the linked list to a :class:`list`. 

769 

770 Optionally, the resulting list can be constructed in reverse order. 

771 

772 :param reverse: Optional parameter, if ``True`` return in reversed order, otherwise in normal order. 

773 :return: A list (array) of this linked list's values. 

774 """ 

775 if self._count == 0: 

776 return [] 

777 elif reverse: 

778 return [n._value for n in self.IterateFromLast()] 

779 else: 

780 return [n._value for n in self.IterateFromFirst()] 

781 

782 def ToTuple(self, reverse: bool = False) -> Tuple[Node[_NodeKey, _NodeValue], ...]: 

783 """ 

784 Convert the linked list to a :class:`tuple`. 

785 

786 Optionally, the resulting tuple can be constructed in reverse order. 

787 

788 :param reverse: Optional parameter, if ``True`` return in reversed order, otherwise in normal order. 

789 :return: A tuple of this linked list's values. 

790 """ 

791 if self._count == 0: 

792 return tuple() 

793 elif reverse: 

794 return tuple(n._value for n in self.IterateFromLast()) 

795 else: 

796 return tuple(n._value for n in self.IterateFromFirst()) 

797 

798 # Copy 

799 # Sort 

800 

801 # merge lists 

802 # append / prepend lists 

803 # split list 

804 

805 # Remove at position (= __delitem__) 

806 # Remove by predicate (n times) 

807 

808 # Insert at position (= __setitem__) 

809 

810 # insert tuple/list/linkedlist at begin 

811 # insert tuple/list/linkedlist at end 

812 

813 # Find by position (= __getitem__) 

814 # Find by predicate from left (n times) 

815 # Find by predicate from right (n times) 

816 

817 # Count by predicate 

818 

819 # slice by start, length from right -> new list 

820 # slice by start, length from left 

821 # Slice by predicate 

822 

823 # iterate start, length from right 

824 # iterate start, length from left 

825 # iterate by predicate 

826 

827 def __len__(self) -> int: 

828 """ 

829 Returns the number of nodes in the linked list. 

830 

831 :returns: Number of nodes. 

832 """ 

833 return self._count 

834 

835 def __getitem__(self, index: int) -> _NodeValue: 

836 """ 

837 Access a node's value by its index. 

838 

839 :param index: Node index to access. 

840 :return: Node's value at the given index. 

841 :raises ValueError: If parameter 'index' is out of range. 

842 

843 .. note:: 

844 

845 The algorithm starts iterating nodes from the shorter end. 

846 """ 

847 return self.GetNodeByIndex(index)._value 

848 

849 def __setitem__(self, index: int, value: _NodeValue) -> None: 

850 """ 

851 Set the value of node at the given position. 

852 

853 :param index: Index of the node to modify. 

854 :param value: New value for the node's value addressed by index. 

855 """ 

856 self.GetNodeByIndex(index)._value = value 

857 

858 def __delitem__(self, index: int) -> Node[_NodeKey, _NodeValue]: 

859 """ 

860 Remove a node at the given index. 

861 

862 :param index: Index of the node to remove. 

863 :return: Removed node. 

864 """ 

865 node = self.GetNodeByIndex(index) 

866 node.Remove() 

867 return node._value