单链表的实现（python）

采用链表实现顺序表的规则如下：

需要两个类，LNode只有两个变量 elem是保存的元素，next是下一个元素的内存地址, LList类处理增删改查等操作

只写了增加元素的代码，删除修改类似。

增加元素

　　增加元素分为首部，尾部，任意位置三种，

　　首部，首先判断head是否为空，head不为空时将新加的元素的next 指向原head的内存地

　　　　单链表的实现（python）

　　尾部，需要通过扫描找到左后一个元素(next为None的)，直接将最后一个元素的next指向新加入的元素所在的内存地址

　　任意位置，例如A，B两个元素的计数分别为5，6（从0开始计数）,现要将A和B之间插入一个C元素。示例图如下：

　　　单链表的实现（python）

修改元素：

　　首部：如果只有一个一个则直接替换，如果大于1则将原首部的next设为None, 将新加元素的next设为下一个元素的内存地址

　　尾部：如果只有一个一个则直接替换，如果大于1则将 i-1 个元素的next指向新加入元素的内存地址 (i为索引的最大值)　

　　任意位置：加入只有A,B,C三个元素，现在用D元素替换掉B元素。将A的next指向D的内存地址，B的next设置None, D的next指向C的内存地址

　　　单链表的实现（python）

删除元素：

　　首部：新的head为原首部的next，原首部的next设为None。

　　尾部：先扫描元素找到倒数第二个元素将 i - 1 的next设为None即可（i为最大元素值）

　　任意位置：先判断替换索引值是否合法，例如A,B,C三元素要去除B，扫描找到位置后，将A的next指向C的内存地址，B的next设为None

# -*- coding: utf-8 -*-


class LNode():
    def __init__(self, elem, next_=None):
        self.elem = elem
        self.next = next_


class LLlist():
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head == None

    def count(self):
        # 计数
        count = 1
        current = self.head
        while current.next != None:
            count += 1
            current = current.next
        return count
    
    def h_add(self, elem):
        """
        向头部添加
        分三步：1、将新的值elem 加入结点，2、将新的指针指向原head，3、self.head值更新为新的结点
        """
        current = LNode(elem)
        if self.is_empty():
            self.head = current            
        else:
            current.next = self.head
            self.head = current

    def insert(self, index, elem):
        """
        任意位置插入
        index：索引
        elem：插入元素
        列：A,B为两个相邻元素对应索引为0，1， C为要插入元素
        分步：1、A.next = C所在内存空间的地址。2、C.next = B位置所在的内存地址
        """
        if index < 0 or index > self.count() - 1:
            raise IndexError('插入的位置不合法!')
        current = self.head
        add = LNode(elem)
        num = 0
        while current.next != None:
            if num == index - 1:
                up = current.next
                current.next = add
            num += 1
            if index == num:
                add.next = up
                break
            current = current.next

    def travel(self):
        current = self.head
        while current != None:
            print current.elem
            current = current.next
            
    def h_end(self, elem):
        # 向尾部添加
        current1 = LNode(elem)
        current2 = self.head
        if self.head == None:
            self.head = current1
        else:
            while current2.next != None:
                current2 = current2.next
            current2.next = current1


a = LLlist()
for x in range(1,3):
    a.h_add(x)
a.h_end(200)
a.h_add('aaa')
a.insert(2,300)
a.travel()

单链表的实现（python）

相关推荐