## python数据结构之链表详解

| |
[ 所属分类 开发（python） | 发布者 店小二04 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

data为自定义的数据，next为下一个节点的地址。

python实现链表

class Node:
'''
data: 节点保存的数据
_next: 保存下一个节点对象
'''
def __init__(self, data, pnext=None):
self.data = data
self._next = pnext
def __repr__(self):
'''

print为输出data
'''
return str(self.data)

def isEmpty(self):
return (self.length == 0

def append(self, dataOrNode):
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
self.length += 1
else:
while node._next:
node = node._next
node._next = item
self.length += 1

#删除一个节点之后记得要把链表长度减一
def delete(self, index):
if self.isEmpty():
print "this chain table is empty."
return
if index < 0 or index >= self.length:
print 'error: out of index'
return
#要注意删除第一个节点的情况
#如果有空的头节点就不用这样
#但是我不喜欢弄头节点
if index == 0:
self.length -= 1
return
#prev为保存前导节点
#node为保存当前节点
#当j与index相等时就
#相当于找到要删除的节点
j = 0
while node._next and j < index:
prev = node
node = node._next
j += 1
if j == index:
prev._next = node._next
self.length -= 1

def update(self, index, data):
if self.isEmpty() or index < 0 or index >= self.length:
print 'error: out of index'
return
j = 0
while node._next and j < index:
node = node._next
j += 1
if j == index:
node.data = data

def getItem(self, index):
if self.isEmpty() or index < 0 or index >= self.length:
print "error: out of index"
return
j = 0
while node._next and j < index:
node = node._next
j += 1
return node.data

def getIndex(self, data):
j = 0
if self.isEmpty():
print "this chain table is empty"
return
while node:
if node.data == data:
return j
node = node._next
j += 1
if j == self.length:
return

def insert(self, index, dataOrNode):
if self.isEmpty():
print "this chain tabale is empty"
return
if index < 0 or index >= self.length:
print "error: out of index"
return
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if index == 0:
self.length += 1
return
j = 0
while node._next and j < index:
prev = node
node = node._next
j += 1
if j == index:
item._next = node
prev._next = item
self.length += 1

def clear(self):
self.length = 0

# -*- coding:utf8 -*-
#/usr/bin/env python
class Node(object):
def __init__(self, data, pnext = None):
self.data = data
self._next = pnext
def __repr__(self):
return str(self.data)
class ChainTable(object):
def __init__(self):
self.length = 0
def isEmpty(self):
return (self.length == 0)
def append(self, dataOrNode):
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
self.length += 1
else:
while node._next:
node = node._next
node._next = item
self.length += 1
def delete(self, index):
if self.isEmpty():
print "this chain table is empty."
return
if index < 0 or index >= self.length:
print 'error: out of index'
return
if index == 0:
self.length -= 1
return
j = 0
while node._next and j < index:
prev = node
node = node._next
j += 1
if j == index:
prev._next = node._next
self.length -= 1
def insert(self, index, dataOrNode):
if self.isEmpty():
print "this chain tabale is empty"
return
if index < 0 or index >= self.length:
print "error: out of index"
return
item = None
if isinstance(dataOrNode, Node):
item = dataOrNode
else:
item = Node(dataOrNode)
if index == 0:
self.length += 1
return
j = 0
while node._next and j < index:
prev = node
node = node._next
j += 1
if j == index:
item._next = node
prev._next = item
self.length += 1
def update(self, index, data):
if self.isEmpty() or index < 0 or index >= self.length:
print 'error: out of index'
return
j = 0
while node._next and j < index:
node = node._next
j += 1
if j == index:
node.data = data
def getItem(self, index):
if self.isEmpty() or index < 0 or index >= self.length:
print "error: out of index"
return
j = 0
while node._next and j < index:
node = node._next
j += 1
return node.data
def getIndex(self, data):
j = 0
if self.isEmpty():
print "this chain table is empty"
return
while node:
if node.data == data:
return j
node = node._next
j += 1
if j == self.length:
return
def clear(self):
self.length = 0
def __repr__(self):
if self.isEmpty():
return "empty chain table"
nlist = ''
while node:
nlist += str(node.data) + ' '
node = node._next
return nlist
def __getitem__(self, ind):
if self.isEmpty() or ind < 0 or ind >= self.length:
print "error: out of index"
return
return self.getItem(ind)
def __setitem__(self, ind, val):
if self.isEmpty() or ind < 0 or ind >= self.length:
print "error: out of index"
return
self.update(ind, val)
def __len__(self):
return self.length