链表（单链表、双链表）

前言：链表是算法中比较难理解的部分，本博客记录单链表、双链表学习，理解节点和指针的使用，主要内容包括：使用python创建链表、实现链表常见的操作。

目录

单链表

双链表

---

单链表

引入链表的背景：

先来看一下数据，数组是一块连续的区域，需要预留空间。

链表，是一种线性表，线性表包括顺序表、链表，但链表不像顺序表一样连续地存储数据，而是在每个节点里存放下一个节点的位置信息（地址）。

单链表，第一个节点是头节点，最后一个节点是尾节点。

操作链表时，需要注意特殊的情况：

1. 空链表
2. 只有一个头节点没有尾节点的链表，头节点地址指向空
3. 有一个头节点，接着连接一个尾节点，没有中间节点

使用python语言创建一个单链表

需要实现以下功能：

• 实现判断链表是否为空
• 计算链表的长度
• 在链表头部添加元素
• 在链表尾部添加元素
• 在链表的指定位置添加元素
• 删除指定元素的节点
• 判断节点是否存在

class Node(object):
    def __init__(self, elem):
        # 节点
        self.elem = elem
        self.next = None
 
 
# 单链表
class SingleLinkList(object):
    def __init__(self, node=None):
        self.__head = node
 
    # 判断链表是否为空
    def is_empty(self):
        return self.__head == None
 
    # 链表的长度
    def length(self):
        # cur游标用来遍历节点
        cur = self.__head
        count = 1
        while cur != None:
            count += 1
            cur = cur.next
        return count
 
    # 链表的遍历
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
 
    # 头部添加元素
    def add(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node
 
    # 尾部添加元素
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
        pass
 
    # 指定位置添加元素
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            pre = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                pre = pre.next
            #     当循环退出后 pre指向pos-1
            node = Node(item)
            node.next = pre.next
            pre.next = node
 
    # 删除元素 找到具体的数据删除
    def remove(self, item):
        cur = self.__head
        pre = None
        while cur != None:
            if cur.elem == item:
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
 
    # 查找节点是否存在
    def search(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False

双链表

双链表比单链表多了个前驱节点

使用python语言创建一个双链表

需要实现以下功能：

• 实现判断链表是否为空
• 计算链表的长度
• 在链表头部添加元素
• 在链表尾部添加元素
• 在链表的指定位置添加元素
• 删除指定元素的节点
• 判断节点是否存在

 

class Node(object):
    def __init__(self, item):
        self.elem = item
        self.next = None
        self.prev = None
 
 
class DoubleLinkList(object):
    # 双链表
    def __init__(self, node=None):
        self.__head = node
 
    # 判断链表是否为空
    def is_empty(self):
        return self.__head == None
 
    # 链表的长度
    def length(self):
        # cur游标用来遍历节点
        cur = self.__head
        count = 1
        while cur != None:
            count += 1
            cur = cur.next
        return count
 
    # 链表的遍历
    def travel(self):
        cur = self.__head
        while cur != None:
            print(cur.elem, end=" ")
            cur = cur.next
 
    # 头部添加元素
    def add(self, item):
        node = Node(item)
        node.next = self.__head
        self.__head = node
        node.next.prev = node
 
    # 尾部添加元素
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self.__head = node
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node
            node.prev = cur
        pass
 
    # 指定位置添加元素
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < (pos - 1):
                count += 1
                cur = cur.next
            #     当循环退出后 pre指向pos
            node = Node(item)
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node
 
    # 删除元素 找到具体的数据删除
    def remove(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                if cur == self.__head:
                    self.__head = cur.next
                    if cur.next:
                        # 判断链表是否只有一个节点
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next
 
    # 查找节点是否存在
    def search(self, item):
        cur = self.__head
        while cur != None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False