python单链表实现代码实例

yipeiwu_com5年前Python基础

链表的定义:
链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址。由于每个结点都包含了可以链接起来的地址信息,所以用一个变量就能够访问整个结点序列。也就是说,结点包含两部分信息:一部分用于存储数据元素的值,称为信息域;另一部分用于存储下一个数据元素地址的指针,称为指针域。链表中的第一个结点的地址存储在一个单独的结点中,称为头结点或首结点。链表中的最后一个结点没有后继元素,其指针域为空。  

python单链表实现代码:

复制代码 代码如下:

#!/usr/bin/python
# -*- coding: utf-8 -*-

class Node(object):
    def __init__(self,val,p=0):
        self.data = val
        self.next = p

class LinkList(object):
    def __init__(self):
        self.head = 0

    def __getitem__(self, key):

        if self.is_empty():
            print 'linklist is empty.'
            return

        elif key <0  or key > self.getlength():
            print 'the given key is error'
            return

        else:
            return self.getitem(key)

 

    def __setitem__(self, key, value):

        if self.is_empty():
            print 'linklist is empty.'
            return

        elif key <0  or key > self.getlength():
            print 'the given key is error'
            return

        else:
            self.delete(key)
            return self.insert(key)

    def initlist(self,data):

        self.head = Node(data[0])

        p = self.head

        for i in data[1:]:
            node = Node(i)
            p.next = node
            p = p.next

    def getlength(self):

        p =  self.head
        length = 0
        while p!=0:
            length+=1
            p = p.next

        return length

    def is_empty(self):

        if self.getlength() ==0:
            return True
        else:
            return False

    def clear(self):

        self.head = 0


    def append(self,item):

        q = Node(item)
        if self.head ==0:
            self.head = q
        else:
            p = self.head
            while p.next!=0:
                p = p.next
            p.next = q


    def getitem(self,index):

        if self.is_empty():
            print 'Linklist is empty.'
            return
        j = 0
        p = self.head

        while p.next!=0 and j <index:
            p = p.next
            j+=1

        if j ==index:
            return p.data

        else:

            print 'target is not exist!'

    def insert(self,index,item):

        if self.is_empty() or index<0 or index >self.getlength():
            print 'Linklist is empty.'
            return

        if index ==0:
            q = Node(item,self.head)

            self.head = q

        p = self.head
        post  = self.head
        j = 0
        while p.next!=0 and j<index:
            post = p
            p = p.next
            j+=1

        if index ==j:
            q = Node(item,p)
            post.next = q
            q.next = p


    def delete(self,index):

        if self.is_empty() or index<0 or index >self.getlength():
            print 'Linklist is empty.'
            return

        if index ==0:
            q = Node(item,self.head)

            self.head = q

        p = self.head
        post  = self.head
        j = 0
        while p.next!=0 and j<index:
            post = p
            p = p.next
            j+=1

        if index ==j:
            post.next = p.next

    def index(self,value):

        if self.is_empty():
            print 'Linklist is empty.'
            return

        p = self.head
        i = 0
        while p.next!=0 and not p.data ==value:
            p = p.next
            i+=1

        if p.data == value:
            return i
        else:
            return -1


l = LinkList()
l.initlist([1,2,3,4,5])
print l.getitem(4)
l.append(6)
print l.getitem(5)

l.insert(4,40)
print l.getitem(3)
print l.getitem(4)
print l.getitem(5)

l.delete(5)
print l.getitem(5)

l.index(5)

结果:

5
6
4
40
5
6

相关文章

python 直接赋值和copy的区别详解

直接赋值和copy的区别: 直接赋值:其实就是对象的引用(别名)。 浅拷贝(copy):拷贝父对象,不会拷贝对象的内部的子对象。 深拷贝(deepcopy): copy 模...

Python实现的网页截图功能【PyQt4与selenium组件】

本文实例讲述了Python实现的网页截图功能。分享给大家供大家参考,具体如下: 方法一、使用PyQt4的QtWebKit组件 #!/usr/bin/env python # -*-...

python进程管理工具supervisor使用实例

python进程管理工具supervisor使用实例

平时我们写个脚本,要放到后台执行去,我们怎么做呢? 复制代码 代码如下: nohup python example.py 2>&1 /dev/null & 用tumx或者scre...

Python中异常重试的解决方案详解

前言 大家在做数据抓取的时候,经常遇到由于网络问题导致的程序保存,先前只是记录了错误内容,并对错误内容进行后期处理。 原先的流程: def crawl_page(url): pa...

python之PyQt按钮右键菜单功能的实现代码

python之PyQt按钮右键菜单功能的实现代码

实现效果如下图: 这篇文字主要写了两方面的内容: 第一是按钮的自定义,第二是右键菜单的使用,不仅是按钮的右键菜单,其他一些控件的右键菜单也可以类似创建和使用。 关于右键菜单则是QMe...