线性表List

数组array是基本的数据结构，但它的功能有限，线性表list可以认为是扩展了功能的数组。可以自动调整大小。添加和删除元素不需要其他元素移位。

根据指针数量和指向的不同，线性表分为单向链表、双向链表和循环链表。

一、单向链表

单项链表有一个头指针，指向链表的第一个元素，除最后一个元素外，其它元素都有一个指针指向其后的元素。如图：

这种结构简单有效，可以非常方便的对链表进行遍历、查询、添加和删除元素。

class ListNode:

    def __init__(self,data):

        self.data=data

        self.next=None

class LinkList :

    def __init__( self ):

        self.head = None

        self._size = 0

    def is_empty(self):

        return self.head is None

    def __len__( self ):

        return self._size

    def __contains__( self, target ):

        curNode = self.head

        while curNode is not None and curNode.data != target :

            curNode = curNode.next

        return curNode is not None

    def search(self,target):

        curNode =self.head

        while curNode is not None and curNode.data !=target:

            curNode=curNode.next

        return curNode is not None

    def pre_add(self,data ):

        newNode = ListNode(data )

        newNode.next = self.head

        self.head = newNode

        self._size += 1

    def append(self,data):

        newNode=ListNode(data)

        if self.head is None:

            self.head=newNode

            self._size+=1

            return

        curNode=self.head

        while curNode.next is not None:

            curNode=curNode.next

        curNode.next=newNode

        self._size+=1

    def pre_del(self):

        if self.head is None:

            return

        curNode=self.head

        print curNode.data

        self.head=curNode.next

    def pop(self):

        if self.head is None:

            return

        preNode=None

        curNode=self.head

        while curNode.next is not None:

            preNode=curNode

            curNode=curNode.next

        if curNode is self.head:

            print curNode.data

            self.head=None

            self._size-=1

        else:

            print curNode.data

            preNode.next=curNode.next

            self._size -=1    

    def travel(self,head):

        curNode=self.head

        while curNode is not None:

            print curNode.data

            curNode=curNode.next

    def remove( self, data ):

        predNode = None

        curNode = self.head

        while curNode is not None and curNode.data != data :

            predNode = curNode

            curNode = curNode.next

        self._size -= -1

        if curNode is self.head :

            self.head = curNode.next

        else :

            predNode.next = curNode.next

        return curNode.data

if __name__=='__main__':

    test=LinkList()

    for i in range(10):

        test.append(i)

    test.pop()

    test.pop()

    print '*********************'

    test.pre_del()

    test.pre_del()

    print '*********************'

    print test.remove(4)

    print test.remove(5)

    print '*********************'

    test.travel(test.head)

    print test.search(5)

巴特西

线性表List

最新文章

热门文章