#yyds干货盘点#Python线性表-单链表

1. 线性表简介

线性表是一种线性结构,它是由零个或多个数据元素组成的有限序列。线性表的特点是,在一个序列中,除头部和尾部元素外,每个元素都有一个直接前驱和只有一个直接后继,而序列头部元素没有直接前导,序列尾部元素没有直接后继。

[En]

A linear table is a linear structure, which is a finite sequence of zero or more data elements. The characteristic of the linear table is that in a sequence, except for the head and tail elements, each element has one direct precursor and only one direct successor, while the sequence head element has no direct predecessor and the sequence tail element has no direct successor.

数据结构中常见的线性结构有数组、单链表、双链表、循环链表等。线性表中的元素为某种 相同的抽象数据类型。可以是C语言的内置类型或结构体,也可以是C++自定义类型。

2. 数组

数组在实际的物理内存上也是连续存储的,数组有上界和下界。C语言中定义一个数组:

#yyds干货盘点#Python线性表-单链表

数组下标是从0开始的,a[0]对应第一个元素。其中,a[0]称为数组a的下界,a[6]称为数组a的上届。超过这个范围的下标使用数组,将造成 数组越界错误

数组的特点是: 数据连续,支持快速随机访问。

数组分为固定数组与动态数组。其中固定数组的大小必须在编译时就能够确认,动态数组允许在运行时申请数组内存。复杂点的数组是多维数组,多维数组实际上也是通过一维数组来实现的。在C语言中,可以通过malloc来分配动态数组,C++使用new。另外,C++的标准模板库提供了动态数组类型vector以及内置有固定数组类型array。

Python中list可以被认为是封装好的数组。

3. 单向链表

单向链表是链表的一种。链表由节点组成,这些节点包含指向下一个节点的指针,这些节点依次链接到链表。因此,链表在物理内存中通常是不连续的。链表通常包含一个头节点,它不保存实际值,但包含指向存储元素的第一个节点的指针。

[En]

One-way linked list is a kind of linked list. The linked list is made up of nodes, which contain a pointer to the next node, and the nodes are linked to the linked list in turn. As a result, linked lists are usually discontiguous in physical memory. The linked list usually contains a header node, which does not hold the actual value, but contains a pointer to the first node where the element is stored.

#yyds干货盘点#Python线性表-单链表
class Node():    """    单链表中的节点应该具有两个属性:val 和 next。    val 是当前节点的值,    next 是指向下一个节点的指针/引用。    """    def __init__(self, value):        # 存放元素数据        self.val = value        # next是下一个节点的标识        self.next = None

设计链表的实现

您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:​ ​val​​​ 和 ​ ​next​​​。​ ​val​​​ 是当前节点的值,​ ​next​​​ 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 ​ ​prev​​ 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链接列表类中实现以下函数:

[En]

Implement these functions in the linked list class:

  • get(index):获取链表中第 ​ ​index​​​ 个节点的值。如果索引无效,则返回​ ​-1​​。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 ​ ​val​​ 的节点。插入后,新节点将成为链表的第一个节点。

#yyds干货盘点#Python线性表-单链表
  • addAtTail(val):将值为 ​ ​val​​ 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 ​ ​index​​​ 个节点之前添加值为 ​ ​val​​​ 的节点。如果 ​ ​index​​​ 等于链表的长度,则该节点将附加到链表的末尾。如果 ​ ​index​​ 大于链表长度,则不会插入节点。
  • deleteAtIndex(index):如果索引 ​ ​index​​​ 有效,则删除链表中的第 ​ ​index​​ 个节点。

#yyds干货盘点#Python线性表-单链表
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Author : Young
@File : linked_list2.py
@version : 1.0
@Time : 2019/4/5 11:06
Description about this file:

"""


class Node():
"""
单链表中的节点应该具有两个属性:val 和 next。
val 是当前节点的值,
next 是指向下一个节点的指针/引用。
"""

def __init__(self, value):
# 存放元素数据
self.val = value
# next是下一个节点的标识
self.next = None


class SingleLinkList():
def __init__(self, node=None):
# 头节点定义为私有变量
self._head = node

def is_empty(self):
# 判断链表是否为空
if self._head is None:
return True
else:
return False

def get(self, index: int) -> int:
"""
获取链表中第 index 个节点的值。如果索引无效,则返回-1
:param index: 索引值
:return:
"""
if self._head is None:
return -1
cur = self._head
for i in range(index):
if cur.next is None:
return -1
cur = cur.next
return cur.val

def length(self):
"""
cur游标,用来移动遍历节点
count用来计数
:return: 返回链表的长度
"""
cur = self._head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count

def travel(self):
"""
遍历整个链表
:return:
"""
cur = self._head
while cur is not None:
print(cur.elem, end=' ')
cur = cur.next

def add_at_head(self, val: int) -> None:
"""
在头部添加一个节点
:param val:
:return: None
"""
# 先创建一个保存item值的节点
node = Node(val)
# 判断链表是否为空
if self._head is None:
self._head = node
else:
# 将新节点的链接域next指向头节点,即_head指向的位置
node.next = self._head
# 将链表的头_head指向新节点
self._head = node

def add_at_tail(self, val: int) -> None or int:
"""
在尾部添加一个节点
:param item:
:return:
"""
node = Node(val)
# 若链表为空,直接将该节点作为链表的第一个元素
if self._head is None:
self._head = node
else:
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node

def add_at_index(self, index: int, val: int) -> None:
"""
在指定位置pos添加节点
pos从0开始
:param index:
:param val:
:return:
"""
# 若指定位置pos为第一个元素之前,则执行头部插入
if index 0:
self.add_at_head(val)
# 若指定位置超过链表尾部,则执行尾部插入
elif index >= self.length():
self.add_at_tail(val)
# 找到指定位置
else:
# pre用来指向指定位置pos的前一个位置pos-1,初始从头节点开始移动到指定位置
pre = self._head
count = 0
node = Node(val)
# 在目标节点的前一位停下
while count < (index - 1):
count += 1
pre = pre.next
# 先将新节点node的next指向插入位置的节点
node.next = pre.next
# 将插入位置的前一个节点的next指向新节点
pre.next = node

def delete_at_index(self, index: int) -> None or int:
"""
如果索引 index 有效,则删除链表中的第 index 个节点。
:param index: 对应的索引值
:return: -1表示为异常
"""
pre = None
cur = self._head
if index is 0:
self._head = None
for i in range(index):
if cur.next is None:
# raise IndexError("越界")
return -1
pre = cur
cur = pre.next
else:
pre.next = cur.next

def search(self, val: int) -> True or False:
"""
查找节点是否存在
:param val: 节点的val值
:return:
"""
cur = self._head
while cur is not None:
if cur.val == val:
return True
else:
cur = cur.next
return False


if __name__ == '__main__':
obj = SingleLinkList()
obj.add_at_head(1)
obj.add_at_tail(3)
obj.add_at_index(1, 2)
obj.travel()
obj.delete_at_index(1)
obj.travel()

链表与顺序表的对比

链表失去了随机读取顺序列表的优势。同时,由于增加了节点的指针域,链表的空间开销较大,但存储空间的使用应相对灵活。

[En]

The linked list loses the advantage of random reading of the sequential list. At the same time, due to the addition of the pointer domain of nodes, the linked list has a large space overhead, but the use of storage space should be relatively flexible.

链表和顺序表的各种操作复杂性如下:

[En]

The various operational complexities of linked lists and sequential lists are as follows:

操作

链表

顺序表

访问元素

O(n)

O(1)

在头部插入/删除

O(1)

O(n)

在尾部插入/删除

O(n)

O(1)

在中间插入/删除

O(n)

O(n)

Original: https://blog.51cto.com/u_15452495/5583977
Author: 瑞士卷心菜
Title: #yyds干货盘点#Python线性表-单链表

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/500689/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球