脚本之家,脚本语言编程技术及教程分享平台!
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Python - Python数据结构之双向链表的定义与使用方法示例

Python数据结构之双向链表的定义与使用方法示例

2021-01-05 00:21yupeng Python

这篇文章主要介绍了Python数据结构之双向链表的定义与使用方法,结合实例形式分析了Python双向链表的概念、原理、使用方法及相关注意事项,需要的朋友可以参考下

本文实例讲述了Python数据结构双向链表的定义与使用方法。分享给大家供大家参考,具体如下:

和单链表类似,只不过是增加了一个指向前面一个元素的指针而已。

示意图:

Python数据结构之双向链表的定义与使用方法示例

python 实现代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#!/usr/bin/python
# -*- coding: utf-8 -*-
class Node(object):
  def __init__(self,val,p=0):
    self.data = val
    self.next = p
    self.prev = 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
      node.prev = p
      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
      q.prev = p
  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.prev = post
      q.next = p
      p.prev = q
  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
      p.next.prev = post
  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 "服务器之家测试结果:"
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)

结果为;

Python数据结构之双向链表的定义与使用方法示例

和单链表结果一样。

PS:双向链表就是将链表首尾相接。

希望本文所述对大家Python程序设计有所帮助。

原文链接:https://www.cnblogs.com/yupeng/p/3413800.html

延伸 · 阅读

精彩推荐