python单链表实现代码实例

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

python单链表实现代码：

#!/usr/bin/python<BR># -*- coding: utf-8 -*-</P><P>class Node(object):<BR>    def __init__(self,val,p=0):<BR>        self.data = val<BR>        self.next = p</P><P>class LinkList(object):<BR>    def __init__(self):<BR>        self.head = 0</P><P>    def __getitem__(self, key):</P><P>        if self.is_empty():<BR>            print 'linklist is empty.'<BR>            return</P><P>        elif key  self.getlength():<BR>            print 'the given key is error'<BR>            return</P><P>        else:<BR>            return self.getitem(key)</P><P> </P><P>    def __setitem__(self, key, value):</P><P>        if self.is_empty():<BR>            print 'linklist is empty.'<BR>            return</P><P>        elif key  self.getlength():<BR>            print 'the given key is error'<BR>            return</P><P>        else:<BR>            self.delete(key)<BR>            return self.insert(key)</P><P>    def initlist(self,data):</P><P>        self.head = Node(data[0])</P><P>        p = self.head</P><P>        for i in data[1:]:<BR>            node = Node(i)<BR>            p.next = node<BR>            p = p.next</P><P>    def getlength(self):</P><P>        p =  self.head<BR>        length = 0<BR>        while p!=0:<BR>            length+=1<BR>            p = p.next</P><P>        return length</P><P>    def is_empty(self):</P><P>        if self.getlength() ==0:<BR>            return True<BR>        else:<BR>            return False</P><P>    def clear(self):</P><P>        self.head = 0</P><P><BR>    def append(self,item):</P><P>        q = Node(item)<BR>        if self.head ==0:<BR>            self.head = q<BR>        else:<BR>            p = self.head<BR>            while p.next!=0:<BR>                p = p.next<BR>            p.next = q</P><P><BR>    def getitem(self,index):</P><P>        if self.is_empty():<BR>            print 'Linklist is empty.'<BR>            return<BR>        j = 0<BR>        p = self.head</P><P>        while p.next!=0 and j <index:<BR>            p = p.next<BR>            j+=1</P><P>        if j ==index:<BR>            return p.data</P><P>        else:</P><P>            print 'target is not exist!'</P><P>    def insert(self,index,item):</P><P>        if self.is_empty() or indexself.getlength():<BR>            print 'Linklist is empty.'<BR>            return</P><P>        if index ==0:<BR>            q = Node(item,self.head)</P><P>            self.head = q</P><P>        p = self.head<BR>   <strong>本文来源gaodai#ma#com搞@@代~&码*网2</strong>     post  = self.head<BR>        j = 0<BR>        while p.next!=0 and j<index:<BR>            post = p<BR>            p = p.next<BR>            j+=1</P><P>        if index ==j:<BR>            q = Node(item,p)<BR>            post.next = q<BR>            q.next = p</P><P><BR>    def delete(self,index):</P><P>        if self.is_empty() or indexself.getlength():<BR>            print 'Linklist is empty.'<BR>            return</P><P>        if index ==0:<BR>            q = Node(item,self.head)</P><P>            self.head = q</P><P>        p = self.head<BR>        post  = self.head<BR>        j = 0<BR>        while p.next!=0 and j<index:<BR>            post = p<BR>            p = p.next<BR>            j+=1</P><P>        if index ==j:<BR>            post.next = p.next</P><P>    def index(self,value):</P><P>        if self.is_empty():<BR>            print 'Linklist is empty.'<BR>            return</P><P>        p = self.head<BR>        i = 0<BR>        while p.next!=0 and not p.data ==value:<BR>            p = p.next<BR>            i+=1</P><P>        if p.data == value:<BR>            return i<BR>        else:<BR>            return -1</P><P><BR>l = LinkList()<BR>l.initlist([1,2,3,4,5])<BR>print l.getitem(4)<BR>l.append(6)<BR>print l.getitem(5)</P><P>l.insert(4,40)<BR>print l.getitem(3)<BR>print l.getitem(4)<BR>print l.getitem(5)</P><P>l.delete(5)<BR>print l.getitem(5)</P><P>l.index(5)<BR>

结果：

5
6
4
40
5
6

喜欢 (0)赏

[搞代码]

分享 (0)