数据结构与算法-(10)---列表(List)
数据结构与算法-(10)---列表(List)
列表(List)
列表是Python中的一种数据类型，用于存储一组有序的数据。列表中可以存储任意类型的数据，包括数字、字符串、布尔值等。列表以中括号 [ ] 表示，其中的每个元素之间用逗号分隔，例如：
my_list = [1, 2, 3, 4, 5]上述代码创建了一个名为 my_list 的列表，其中包含了整数 1、2、3、4 和 5。可以使用索引访问列表中的元素，例如 my_list[0] 访问列表中的第一个元素。列表支持许多常用的操作，如添加元素、删除元素、排序等。
但并不是所有的编程语言都提供了List数据类型有时候需要程序员自己实现。
列表:是一种数据项按照相对位置存放的数据集
特别的，被称为“无序表unordered list”其中数据项只按照存放位置来索引，如第1个、第2个....."、最后一个等。(为了简单起见，假设表中不存在重复数据项)
如一个考试分数的集合“54，26，93，1777和31”
如果用无序表来表示，就是[54，26，9317, 77, 31]
采用链表实现无序表
采用链表实现无序表的主要原因是，链表具有动态性和灵活性。当我们需求插入或删除元素时，链表可以快速地进行操作，而不需要进行大量的数据移动。此外，链表还可以通过动态分配内存空间来适应数据的变化，这使得无序表可以处理不同大小的数据集。
另外，链表实现无序表还有以下优点：
- 内存使用效率高：链表只需要分配和使用存储空间，而不需要事先设置固定的存储大小，这可以节省内存空间。
- 适用于大型数据集：链表可以处理大量的数据，因为它们不需要在内存中保持连续的存储空间，而是可以分散在内存中的不同区域。
- 可以有效地处理插入和删除操作：链表的插入和删除操作很快，因为它们只需要修改指针，而不需要移动元素。
链表是一种非常适合实现无序表的数据结构，因为它具有动态性，灵活性，高效性和内存使用效率高等优点。
无序表(元素之间没有顺序,但是有位置顺序)
列表
Python 中往列表添加数据,不能灵活添加,因为列表不具有连续的空间
所以元素4不能添加到列表里.
链表
由于链表( Linked List )含 pointer(指针) 所以链表可以利用碎片化空间将数据传入到空格处,
即使被其它元素占领了内存空间
# 通过链表实现 无序表-列表
#列表 和 链表 都是无序表 unordered list
#实现链表
class Node:
def __init__(self,init_data):
self.data = init_data
self.next = None
#获得数据项
def get_data(self):
return self.data
#获得节点
def get_next(self):
return self.next
#设置数据项
def set_data(self,new_data):
self.data = new_data
#设置节点
def set_next(self,new_next):
self.next = new_next
#结点示例
temp = Node(93)
print(temp.get_data())链表的实现
可以采用 链接结点 的方式来构建数据集 实现无序表
链表的第一个 和 最后一个 节点最重要
如果想访问到链表中的所有节点,就必须从第一个节点沿链接遍历下去.
Unordered List - 无序表
箭头所指为表头
最快捷的就是从表头开始(相当于insert[0]),
但是之前列表实现inser[0]的时间复杂度是O(n),
而链表是O(1)
结点(node): 为了组织链表而引入的一个结构，除了保存我们的元素之外，还会保存指向下一个结点的引用
当前结点(current / cur): 表示链表中某个结点。 前驱结点(previous / prev): 表示链表中某个结点的前一个结点；头结点没有前驱结点。 后继结点(next): 表示链表中某个结点的后一个结点；尾结点没有后继结点。
链表的头结点, 链表最开始的节点~ 尤其是对单链表来说, 只要知道了链表的头结点就可以获取到链表的所有的元素！ 通常情况下，特别喜欢用头结点来代指整个链表~
Add方法
思路步骤如下:
#为item数据项生成一个结点-Node 叫做item
def add(self,item):
#然后将这个结点命名为临时变量
temp = Node(item)
#将下一个临时结点设置为表头
temp.set_next(self.head)
#表头指向新增加的临时结点
self.head = temp注意:第三第四行代码顺序不能调换,否则会发生链表丢失
size方法
def size(self):
#当前节点设为表头第一个节点
current = self.head
count = 0
while current != None:
count += 1
#将当前节点设为下一个结点的结点,循环往复
current = current.get_next()
#返回结点的个数
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
#判断当前节点数据项是否等于我想要找的数据
if current.getData() == item:
found = True
else:
current = current.get_next()
return foundremove(item)方法
def remove(self,item):
current = self.head
previous = None
found = False
while not found:
if current.get_data == item:
found = True
else:
previous = current
current = current.get_next
if previous == None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())腾讯云开发者
