数据结构之链表与哈希表

一 什么是链表

链表是由一系列节点组成的元素集合。每个节点包含两部分，数据域item和指向一下个节点的指针next。通过节点之间相互连接，最终串联成一个链表

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 二 链表的操作

1 创建链表

头插法：

class Node:
    def __init__(self, item):
        self.item = item
        self.next = None


def create_linklist(li):
    head = Node(li[0])
    for element in li[1:]:
        node = Node(element)
        node.next = head
        head = node
    return head

尾插法：

2 链表的遍历

def print_linklist(lk):
    while lk:
        print(lk.item, end=',')
        lk = lk.next


print_linklist(lk)

3 链表的插入与删除

插入：

p.next = curNode.next
curNode.next = p

删除：

#删除：
p = curNode.next
curNode.next = p.next  #当前节点的下一个指向就指向他下一个的下一个
del p 

 三 双向链表

双链表的每个节点有两个指针：一个指向后一个节点,另一个指向前一个节点。

class Node(object):
    def __init__(self, item=None):
        self.item = item
        self.next = None
        self.prior = None

1 双向链表的结点插入

p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p

2 双向链表的删除

p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p

 四 哈希表

哈希表是一个通过哈希函数来计算数据存储位置的数据结构，通常支持如下操作：

• insert(key, value):插入键值对(key,value)
• get(key): 如果存在键为key的键值对则返回其value, 否则返回空值
• delete(key): 删除键为key的键值对

1 直接寻址表

当关键字的全域U比较小时，直接寻址是一种简单而有效的方法。

 

直接寻址技术缺点：　

• 当域U很大时，需要消耗大量内存，很不实际
• 如果域U很大而实际出现的key很少，则大量空间被浪费
• 无法处理关键字不是数字的情况

2 哈希

改进直接寻址表：哈希（Hashing）

• 构建大小为m的寻址表T
• key为k的元素放到h(k)位置上
• h(k)是一个函数，其将域U映射到表T[0,1,...,m-1]

哈希表（Hash Table，又称为散列表），是一种线性表的存储结构。哈希表由一个直接寻址表和一个哈希函数组成。哈希函数h(k)将元素关键字k作为自变量，返回元素的存储下标。

假设有一个长度为7的哈希表，哈希函数h(k)=k%7。元素集合{14,22,3,5}的存储方式如下图。

比如h(k)=k%7, h(0)=h(7)=h(14)=...

 

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄