# Basic Data Structure
Implementation of basic sata structures in Python
Supported python versions: `3.9` → `3.12`
Including:
1. [Stack](#stack)
2. [Linked list](#linked-list)
3. [Binary tree](#binary-tree)
Expected data structures in future versions:
1. Queue
2. Double-ended queue
3. Actual binary tree class (now we have `TreeNode` class only)
4. Red-black tree
# Stack
A stack is a data type that serves as a collection of elements with two main operations –
`push` (adds an element to the collection), and `pop` (removes the most recently added element).
## Methods
### `def __init__(*args) -> None`
Initialises stack with given sequence of elements
This sequence (`args`) could be empty, so the stack will be empty at start
Example:
```python
initially_empty_stack = Stack()
not_empty_stack = Stack(1, 2, 3) # the order of elements is stack will be reversed
```
### `def __bool__() -> bool`
Returns `False` if stack is empty
If stack contains at least one element, returns `True`
### `def __len__() -> int`
Returns length (count of elements) of the stack
If the stack is empty, returns `0`
### `def push(value: Any) -> None`
Adds element to the stack
### `def pop() -> Any`
Pops the last element from the stack
Function returns the element and deletes it from the stack
If the stack is empty, this function raises `EmptyStackError` exception
### `def clear() -> None`
Clears the stack (removes all the elements)
Length of the stack afterward will be equal to `0`
## Example
```python
from basic_data_structure import Stack
def init_from_iterable() -> None:
print('Init from iterable:')
stack = Stack(0, 1, 2, 3, 4, 5)
# or like this:
# stack = Stack(*[0, 1, 2, 3, 4, 5])
# stack = Stack(*range(6))
stack.push(6)
stack.push(7)
stack.push(8)
print('Stack length:', len(stack))
while stack:
value = stack.pop()
print(value, end=' ')
print('')
def manual_pushing() -> None:
print('Manual pushing:')
stack = Stack()
stack.push('a')
stack.push('b')
stack.push('c')
while stack:
value = stack.pop()
print(value, end=' ')
print('')
if __name__ == '__main__':
init_from_iterable()
manual_pushing()
```
The `__iter__` and `__next__` methods are not implemented intentionally.
If you want to iterate over a Stack like this `for i in stack`, you're better off
using built-in list instead, because this kind of iteration will implicitly
call `pop()` on each iteration. Therefore, your stack will be empty by the end
of a loop.
It is better to call `pop()` explicitly, so use while loop like this:
```python
while stack:
element = stack.pop()
...
```
# Linked list
A linked list is a linear collection of data elements whose 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 collection of nodes which together represent a sequence.
## Methods
### `def __init__(*args) -> None`
Initialises list with given sequence of elements
This sequence (`args`) could be empty, so the list will be empty at the start
Example:
```python
initially_empty_list = LinkedList()
not_empty_list = LinkedList(1, 2, 3)
```
### `def __bool__() -> bool`
Returns `False` if the list is empty
If list contains at least one element, returns `True`
### `def __len__() -> int`
Returns length (count of elements) in the list
If the list is empty, returns `0`
If the list contains a cycle, raises `ListHasCycleError` exception
This is `O(n)` operation
### `def __getitem__(index: int) -> ListNode`
Returns a node at particular index
If index is out of range, raises `ListIndexError` exception
If the list contains a cycle, raises `ListHasCycleError` exception
Negative indexes supported
Slices are not supported
This is `O(n)` operation
Example:
```python
lst = LinkedList(1, 2, 3)
node = lst[1] # will return node with value `2`
# to retrieve value itself, use attr `value`
print(node.value) # will print out `2`
```
### `def __delitem__(index: int) -> None`
Returns a node at particular index
If index is out of range, raises `ListIndexError` exception
If the list contains a cycle, raises `ListHasCycleError` exception
Negative indexes supported
Slices are not supported
This is `O(n)` operation
Example:
```python
lst = LinkedList(1, 2, 3)
del lst[1] # will delete node with value `2`
```
### `def __reversed__() -> LinkedList`
Returns a reversed copy of the list, the original list remains the same
If the list contains a cycle, raises `ListHasCycleError` exception
This is `O(n)` operation
Example:
```python
lst = LinkedList(1, 2, 3)
rev = reversed(lst) # contains nodes `3` → `2` → `1`
```
### `def __iter__() -> ListNodeIterator`
Returns an iterator, each call `next` method on which returns a `ListNode`
Example:
```python
lst = LinkedList(1, 2, 3)
for node in list:
print(node.value)
```
### `def values() -> ListValueIterator`
Returns an iterator, each call `next` method on which returns a value of a node
Example:
```python
lst = LinkedList(1, 2, 3)
for val in list.values():
print(val)
```
### `def insert(index: int, value: Any) -> None`
Insert a value into given index
Mind, that "value" in this case is not a `ListNode`, but actual value of a future node
If the index is greater than or equal to the length of the list, the element will be inserted
at the end of the list. If the negative index is out of range, the element will be inserted
at the beginning of the list.
If the list contains a cycle, raises `ListHasCycleError` exception
Negative indexes supported
This is `O(n)` operation
Example:
```python
lst = LinkedList(1, 3)
lst.insert(1, 2) # will add element betwin `1` and `3`
lst.insert(len(lst), 4) # will add to the end
lst.insert(100, 5) # will add to the end
lst.insert(-6, 0) # will add to the beginning
lst.insert(-100, -1) # will add to the beginning
```
### `def clear() -> None`
Clears the list (removes all the elements)
The length of the list afterward will be equal to `0`
### `def reverse() -> None`
Reverses the list
Unlike `reversed(lst)`, `lst.reverse()` will rearrange the list itself and will return `None`
If the list contains a cycle, raises `ListHasCycleError` exception
This is `O(n)` operation
Example:
```python
lst = LinkedList(1, 2, 3) # contains nodes `1` → `2` → `3`
lst.reverse() # now contains nodes `3` → `2` → `1`
```
### `def rotate(count: int) -> None`
Rotates (shifts) list to the right or left
If the list contains a cycle, raises `ListHasCycleError` exception
This is `O(n)` operation
Example:
```python
lst = LinkedList(1, 2, 3, 4, 5) # `1` → `2` → `3` → `4` → `5`
lst.rotate(1) # `5` → `1` → `2` → `3` → `4`
lst.rotate(-2) # `2` → `3` → `4` → `5` → `1`
```
### `def has_cycle() -> bool`
Returns `True` if the list contains cycle, `False` otherwise
This is `O(n)` operation
Example:
```python
lst = LinkedList(1, 2, 3, 4, 5)
print(lst.has_cycle()) # False
lst[-1].next = lst[0]
print(lst.has_cycle()) # True
```
### property `def head() -> Optional[ListNode]`
If you want to iterate through the sequence of nodes by yourself, feel free
to use `head` property of the list.
If the list is empty, property will return `None`
### property setter `def head(new_head: Optional[ListNode]) -> None`
Sets new head to the list
Clears the list, if new head is `None`
## Examples
```python
from basic_data_structure import LinkedList
def main():
lst = LinkedList(8, 7, 6, 5, 3)
lst.insert(4, 4)
lst.insert(100, 2)
lst.insert(0, 9)
lst.insert(0, 1)
lst.rotate(-1)
lst.reverse()
for val in lst.values():
print(val, end=' ')
if __name__ == '__main__':
main()
```
If you'd like to create linked list by yourself, you can use `ListNode` class like this, for example:
```python
from basic_data_structure import ListNode
def main():
head = ListNode(1, ListNode(2, ListNode(3)))
while head:
print(head.value, end=' ')
head = head.next
if __name__ == '__main__':
main()
```
## Binary tree
A binary tree is a tree data structure in which each node has at most two children,
referred to as the left child and the right child.
There is no `BinaryTree` class so far in the project, but you can create a tree
using `TreeNode` class like this:
```python
from typing import Generator, Optional
from basic_data_structure import TreeNode
def generate_tree() -> TreeNode:
"""Generate binary tree.
8
┌──────┴───────┐
4 12
┌───┴───┐ ┌───┴───┐
2 6 10 14
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
1 3 5 7 9 11 13 15
"""
return TreeNode(
8,
left=TreeNode(
4,
left=TreeNode(
2,
left=TreeNode(1),
right=TreeNode(3),
),
right=TreeNode(
6,
left=TreeNode(5),
right=TreeNode(7),
),
),
right=TreeNode(
12,
left=TreeNode(
10,
left=TreeNode(9),
right=TreeNode(11),
),
right=TreeNode(
14,
left=TreeNode(13),
right=TreeNode(15),
),
),
)
def dfs(root: Optional[TreeNode]) -> Generator[int, None, None]:
"""Depth-first search."""
if root:
if root.left:
yield from dfs(root.left)
yield root.value
if root.right:
yield from dfs(root.right)
def main():
print('Depth-first search (DFS)')
for data in dfs(root=generate_tree()):
print(data, end=' ')
if __name__ == '__main__':
main()
```
Raw data
{
"_id": null,
"home_page": "https://github.com/mishaga/basic_data_structure",
"name": "basic-data-structure",
"maintainer": null,
"docs_url": null,
"requires_python": "<4.0,>=3.9",
"maintainer_email": null,
"keywords": "data structure, data structures, python data structures, basic data structures",
"author": "Mikhail Shagov",
"author_email": "mishaga@me.com",
"download_url": "https://files.pythonhosted.org/packages/90/72/d2c1e07ea2713a733510f73d01b3689ffdae74c3e1745591959f9ad2a132/basic_data_structure-0.0.5.tar.gz",
"platform": null,
"description": "# Basic Data Structure\n\nImplementation of basic sata structures in Python\n\nSupported python versions: `3.9` \u2192 `3.12`\n\nIncluding:\n1. [Stack](#stack)\n2. [Linked list](#linked-list)\n3. [Binary tree](#binary-tree)\n\nExpected data structures in future versions:\n1. Queue\n2. Double-ended queue\n3. Actual binary tree class (now we have `TreeNode` class only)\n4. Red-black tree\n\n# Stack\n\nA stack is a data type that serves as a collection of elements with two main operations \u2013\n`push` (adds an element to the collection), and `pop` (removes the most recently added element).\n\n## Methods\n\n### `def __init__(*args) -> None`\nInitialises stack with given sequence of elements \nThis sequence (`args`) could be empty, so the stack will be empty at start\n\nExample:\n```python\ninitially_empty_stack = Stack()\nnot_empty_stack = Stack(1, 2, 3) # the order of elements is stack will be reversed\n```\n\n### `def __bool__() -> bool`\nReturns `False` if stack is empty \nIf stack contains at least one element, returns `True`\n\n### `def __len__() -> int`\nReturns length (count of elements) of the stack \nIf the stack is empty, returns `0`\n\n### `def push(value: Any) -> None`\nAdds element to the stack\n\n### `def pop() -> Any`\nPops the last element from the stack \nFunction returns the element and deletes it from the stack\nIf the stack is empty, this function raises `EmptyStackError` exception\n\n### `def clear() -> None`\nClears the stack (removes all the elements) \nLength of the stack afterward will be equal to `0`\n\n## Example\n\n```python\nfrom basic_data_structure import Stack\n\n\ndef init_from_iterable() -> None:\n print('Init from iterable:')\n\n stack = Stack(0, 1, 2, 3, 4, 5)\n # or like this:\n # stack = Stack(*[0, 1, 2, 3, 4, 5])\n # stack = Stack(*range(6))\n stack.push(6)\n stack.push(7)\n stack.push(8)\n print('Stack length:', len(stack))\n\n while stack:\n value = stack.pop()\n print(value, end=' ')\n\n print('')\n\n\ndef manual_pushing() -> None:\n print('Manual pushing:')\n\n stack = Stack()\n stack.push('a')\n stack.push('b')\n stack.push('c')\n\n while stack:\n value = stack.pop()\n print(value, end=' ')\n\n print('')\n\n\nif __name__ == '__main__':\n init_from_iterable()\n manual_pushing()\n```\n\nThe `__iter__` and `__next__` methods are not implemented intentionally. \nIf you want to iterate over a Stack like this `for i in stack`, you're better off\nusing built-in list instead, because this kind of iteration will implicitly\ncall `pop()` on each iteration. Therefore, your stack will be empty by the end\nof a loop. \nIt is better to call `pop()` explicitly, so use while loop like this:\n\n```python\nwhile stack:\n element = stack.pop()\n ...\n```\n\n\n# Linked list\n\nA linked list is a linear collection of data elements whose order is not given by their physical\nplacement in memory. Instead, each element points to the next. It is a data structure consisting\nof a collection of nodes which together represent a sequence.\n\n## Methods\n\n### `def __init__(*args) -> None`\nInitialises list with given sequence of elements \nThis sequence (`args`) could be empty, so the list will be empty at the start\n\nExample:\n```python\ninitially_empty_list = LinkedList()\nnot_empty_list = LinkedList(1, 2, 3)\n```\n\n### `def __bool__() -> bool`\nReturns `False` if the list is empty \nIf list contains at least one element, returns `True`\n\n### `def __len__() -> int`\nReturns length (count of elements) in the list \nIf the list is empty, returns `0` \n\nIf the list contains a cycle, raises `ListHasCycleError` exception \nThis is `O(n)` operation\n\n### `def __getitem__(index: int) -> ListNode`\nReturns a node at particular index\n\nIf index is out of range, raises `ListIndexError` exception \nIf the list contains a cycle, raises `ListHasCycleError` exception \nNegative indexes supported \nSlices are not supported \nThis is `O(n)` operation\n\nExample:\n```python\nlst = LinkedList(1, 2, 3)\nnode = lst[1] # will return node with value `2`\n# to retrieve value itself, use attr `value`\nprint(node.value) # will print out `2`\n```\n\n### `def __delitem__(index: int) -> None`\nReturns a node at particular index\n\nIf index is out of range, raises `ListIndexError` exception \nIf the list contains a cycle, raises `ListHasCycleError` exception \nNegative indexes supported \nSlices are not supported \nThis is `O(n)` operation\n\nExample:\n```python\nlst = LinkedList(1, 2, 3)\ndel lst[1] # will delete node with value `2`\n```\n\n### `def __reversed__() -> LinkedList`\nReturns a reversed copy of the list, the original list remains the same\n\nIf the list contains a cycle, raises `ListHasCycleError` exception \nThis is `O(n)` operation\n\nExample:\n```python\nlst = LinkedList(1, 2, 3)\nrev = reversed(lst) # contains nodes `3` \u2192 `2` \u2192 `1`\n```\n\n### `def __iter__() -> ListNodeIterator`\nReturns an iterator, each call `next` method on which returns a `ListNode`\n\nExample:\n```python\nlst = LinkedList(1, 2, 3)\nfor node in list:\n print(node.value)\n```\n\n### `def values() -> ListValueIterator`\nReturns an iterator, each call `next` method on which returns a value of a node\n\nExample:\n```python\nlst = LinkedList(1, 2, 3)\nfor val in list.values():\n print(val)\n```\n\n### `def insert(index: int, value: Any) -> None`\nInsert a value into given index \nMind, that \"value\" in this case is not a `ListNode`, but actual value of a future node\n\nIf the index is greater than or equal to the length of the list, the element will be inserted\nat the end of the list. If the negative index is out of range, the element will be inserted\nat the beginning of the list.\n\nIf the list contains a cycle, raises `ListHasCycleError` exception \nNegative indexes supported \nThis is `O(n)` operation\n\nExample:\n```python\nlst = LinkedList(1, 3)\nlst.insert(1, 2) # will add element betwin `1` and `3`\nlst.insert(len(lst), 4) # will add to the end\nlst.insert(100, 5) # will add to the end\nlst.insert(-6, 0) # will add to the beginning\nlst.insert(-100, -1) # will add to the beginning\n```\n\n### `def clear() -> None`\nClears the list (removes all the elements) \nThe length of the list afterward will be equal to `0`\n\n### `def reverse() -> None`\nReverses the list \nUnlike `reversed(lst)`, `lst.reverse()` will rearrange the list itself and will return `None`\n\nIf the list contains a cycle, raises `ListHasCycleError` exception \nThis is `O(n)` operation\n\nExample:\n```python\nlst = LinkedList(1, 2, 3) # contains nodes `1` \u2192 `2` \u2192 `3`\nlst.reverse() # now contains nodes `3` \u2192 `2` \u2192 `1`\n```\n\n### `def rotate(count: int) -> None`\nRotates (shifts) list to the right or left\n\nIf the list contains a cycle, raises `ListHasCycleError` exception \nThis is `O(n)` operation\n\nExample:\n```python\nlst = LinkedList(1, 2, 3, 4, 5) # `1` \u2192 `2` \u2192 `3` \u2192 `4` \u2192 `5`\nlst.rotate(1) # `5` \u2192 `1` \u2192 `2` \u2192 `3` \u2192 `4`\nlst.rotate(-2) # `2` \u2192 `3` \u2192 `4` \u2192 `5` \u2192 `1` \n```\n\n### `def has_cycle() -> bool`\nReturns `True` if the list contains cycle, `False` otherwise\n\nThis is `O(n)` operation\n\nExample:\n```python\nlst = LinkedList(1, 2, 3, 4, 5)\nprint(lst.has_cycle()) # False\nlst[-1].next = lst[0]\nprint(lst.has_cycle()) # True\n```\n\n### property `def head() -> Optional[ListNode]`\nIf you want to iterate through the sequence of nodes by yourself, feel free\nto use `head` property of the list. \nIf the list is empty, property will return `None`\n\n### property setter `def head(new_head: Optional[ListNode]) -> None`\nSets new head to the list \nClears the list, if new head is `None`\n\n## Examples\n\n```python\nfrom basic_data_structure import LinkedList\n\n\ndef main():\n lst = LinkedList(8, 7, 6, 5, 3)\n\n lst.insert(4, 4)\n lst.insert(100, 2)\n lst.insert(0, 9)\n lst.insert(0, 1)\n\n lst.rotate(-1)\n lst.reverse()\n\n for val in lst.values():\n print(val, end=' ')\n\n\nif __name__ == '__main__':\n main()\n```\n\nIf you'd like to create linked list by yourself, you can use `ListNode` class like this, for example:\n\n```python\nfrom basic_data_structure import ListNode\n\n\ndef main():\n head = ListNode(1, ListNode(2, ListNode(3)))\n while head:\n print(head.value, end=' ')\n head = head.next\n\n\nif __name__ == '__main__':\n main()\n```\n\n\n## Binary tree\n\nA binary tree is a tree data structure in which each node has at most two children,\nreferred to as the left child and the right child.\n\nThere is no `BinaryTree` class so far in the project, but you can create a tree\nusing `TreeNode` class like this:\n\n```python\nfrom typing import Generator, Optional\n\nfrom basic_data_structure import TreeNode\n\n\ndef generate_tree() -> TreeNode:\n \"\"\"Generate binary tree.\n\n 8\n \u250c\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510\n 4 12\n \u250c\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2510 \u250c\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2510\n 2 6 10 14\n \u250c\u2500\u2534\u2500\u2510 \u250c\u2500\u2534\u2500\u2510 \u250c\u2500\u2534\u2500\u2510 \u250c\u2500\u2534\u2500\u2510\n 1 3 5 7 9 11 13 15\n \"\"\"\n return TreeNode(\n 8,\n left=TreeNode(\n 4,\n left=TreeNode(\n 2,\n left=TreeNode(1),\n right=TreeNode(3),\n ),\n right=TreeNode(\n 6,\n left=TreeNode(5),\n right=TreeNode(7),\n ),\n ),\n right=TreeNode(\n 12,\n left=TreeNode(\n 10,\n left=TreeNode(9),\n right=TreeNode(11),\n ),\n right=TreeNode(\n 14,\n left=TreeNode(13),\n right=TreeNode(15),\n ),\n ),\n )\n\n\ndef dfs(root: Optional[TreeNode]) -> Generator[int, None, None]:\n \"\"\"Depth-first search.\"\"\"\n if root:\n if root.left:\n yield from dfs(root.left)\n\n yield root.value\n\n if root.right:\n yield from dfs(root.right)\n\n\ndef main():\n print('Depth-first search (DFS)')\n for data in dfs(root=generate_tree()):\n print(data, end=' ')\n\n\nif __name__ == '__main__':\n main()\n```\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Implementation of basic sata structures in Python",
"version": "0.0.5",
"project_urls": {
"Homepage": "https://github.com/mishaga/basic_data_structure",
"Issues": "https://github.com/mishaga/basic_data_structure/issues",
"Repository": "https://github.com/mishaga/basic_data_structure"
},
"split_keywords": [
"data structure",
" data structures",
" python data structures",
" basic data structures"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "e8e1ae415673b5c5eff00388fa970de4cdd33569ac7f53bea72a893a80208100",
"md5": "3a11933f6d10e3aa6f0d7082cb101073",
"sha256": "7a779ab2c17dd3582727814c3968f9aa16378e70e56b75a9a2f6f981e7357c0e"
},
"downloads": -1,
"filename": "basic_data_structure-0.0.5-py3-none-any.whl",
"has_sig": false,
"md5_digest": "3a11933f6d10e3aa6f0d7082cb101073",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": "<4.0,>=3.9",
"size": 10093,
"upload_time": "2024-04-30T22:21:58",
"upload_time_iso_8601": "2024-04-30T22:21:58.419372Z",
"url": "https://files.pythonhosted.org/packages/e8/e1/ae415673b5c5eff00388fa970de4cdd33569ac7f53bea72a893a80208100/basic_data_structure-0.0.5-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "9072d2c1e07ea2713a733510f73d01b3689ffdae74c3e1745591959f9ad2a132",
"md5": "ab6a616dbdfd476fb752123e1e54e8c1",
"sha256": "da556ca3c4fec8a61db7b9b7b981931150b333be5161f5990343301e7eaea920"
},
"downloads": -1,
"filename": "basic_data_structure-0.0.5.tar.gz",
"has_sig": false,
"md5_digest": "ab6a616dbdfd476fb752123e1e54e8c1",
"packagetype": "sdist",
"python_version": "source",
"requires_python": "<4.0,>=3.9",
"size": 10653,
"upload_time": "2024-04-30T22:22:00",
"upload_time_iso_8601": "2024-04-30T22:22:00.207464Z",
"url": "https://files.pythonhosted.org/packages/90/72/d2c1e07ea2713a733510f73d01b3689ffdae74c3e1745591959f9ad2a132/basic_data_structure-0.0.5.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-04-30 22:22:00",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "mishaga",
"github_project": "basic_data_structure",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "basic-data-structure"
}
JSON
