Nội dung chính ShowShow
- Node: An individual part of a larger data structure
- Orphaned nodes
- Null node link
- Python Node implementation
- Learn More on Codecademy
- 1. Linked List là cái gì?
- Linked List là tập hợp các nodes được liên kết với nhau. Node sau chứa link đến node trước
- 2. Đặc điểm chính:
- Ưu điểm:
- Nhược điểm
- 3. Thực hiện tạo linked list trên python
- Đầu tiên ta tạo 1 class nodes trên python:
- Thử set dữ liệu cho các node bằng tay:
- Hàm push để thêm dữ liệu cho linked list
- Thử tạo hàm duyệt các phần tử của linked list:
- Ngoài ra ta còn có Double Linked List [Danh sách liên kết đôi]
- 4. Độ phức tạp thuật toán của linked list
Topics
Nodes
- Linked Lists
- Doubly Linked Lists
- Queues
- Stacks
- Hash Maps
- Recursion
- Asymptotic Notation
- Pattern Searching
- Sorting Algorithms
- Brute Force Algorithms
- Trees
- Tree Traversal: Breadth-First Search and Depth-First Search
- Divide and Conquer
- Heaps and Heapsort
- Graphs and Graph Search
- Greedy Algorithms
Node: An individual part of a larger data structure
Nodes are a basic data structure which contain data and one or more links to other nodes. Nodes can be used to represent a tree structure or a linked list. In such structures where nodes are used, it is possible to traverse from one node to another node.
Orphaned nodes
Nodes that have no links pointing to them except for the head node, are considered “orphaned.” In the illustration, if the nodes a2
and a5
are removed, they will be orphaned.
Null node link
Data structures containing nodes have typically two bits of information stored in a node: data and link to next node.
The first part is a value and the second part is an address of sorts pointing to the next node. In this way, a system of nodes is created. A NULL
value in the link part of a node’s info denotes that the path or data structure contains no further nodes.
Python Node implementation
A Node is a data structure that stores a value that can be of any data type and has a pointer to another node. The implementation of a Node class in a programming language such as Python, should have methods to get the value that is stored in the Node, to get the next node, and to set a link to the next node.
class Node:
def __init__[self, value, next_node=None]:
self.value = value
self.next_node = next_node
def set_next_node[self, next_node]:
self.next_node = next_node
def get_next_node[self]:
return self.next_node
def get_value[self]:
return self.value
Learn More on Codecademy
1. Linked List là cái gì? 2 phút đọc
1. Linked List là cái gì?
Linked List là tập hợp các nodes được liên kết với nhau. Node sau chứa link đến node trước
2. Đặc điểm chính:
Ưu điểm:
2. Đặc điểm chính:
Ưu điểm:
- Nhược điểm
- 3. Thực hiện tạo linked list trên python
- Đầu tiên ta tạo 1 class nodes trên python:
- Thử set dữ liệu cho các node bằng tay:
Nhược điểm
- 3. Thực hiện tạo linked list trên python
3. Thực hiện tạo linked list trên python
Đầu tiên ta tạo 1 class nodes trên python:
class Node:
def __init__[self,data]:
self.data = data #Đây là dữ liệu mà ta sẽ lưu trữ trong mỗi node
self.next = None #Đây là con trỏ trỏ đến node tiếp theo trong linked list
Thử set dữ liệu cho các node bằng tay:
node1 = Node["Java"]
node2 = Node["Python"]
node3 = Node["C++"]
node1.next = node2
node2.next = node3
# Ta sẽ được linked list dạng như: Java -> Python -> C++
Hàm push để thêm dữ liệu cho linked list
def push[head, valuetoInsert]:
currentNode = head
while currentNode is not None:
if currentNode.nextNode is None:
currentNode.nextNode = linkedListNode[valuetoInsert]
return head
currentNode = currentNode.nextNode
Thử tạo hàm duyệt các phần tử của linked list:
class Node:
...
def traverse[self]:
node = self # Xác định node đầu tiên hay còn gọi là head node
while node != None:
print node.data # in ra dữ liệu
node = node.next # tiếp tực đến node tiếp theo
Ngoài ra ta còn có Double Linked List [Danh sách liên kết đôi]
class DoublyNode:
def __init__[self, data]:
self.data = data
self.next = None
self.prev = None
4. Độ phức tạp thuật toán của linked list
4. Độ phức tạp thuật toán của linked list
Topics
Nodes