1+ class Node (object ):
2+
3+ def __init__ (self , value = None , next = None , previous = None ):
4+ self .value , self .next , self .previous = value , next , previous
5+
6+ def __str__ (self ):
7+ return '<Node: value:{}, next:{}, previous:{}>' .format (self .value , self .next , self .previous )
8+
9+ __repr__ = __str__
10+
11+
12+ class Circular_Double_LinkedList (object ):
13+
14+ def __init__ (self , maxsize = None ):
15+ self .root = Node ()
16+ self .maxsize = maxsize
17+ self .root .next = self .root
18+ self .root .previous = self .root
19+ self .length = 0
20+
21+ def __len__ (self ):
22+ return self .length
23+
24+ def headnode (self ):
25+ return self .root .next
26+
27+ def tailnode (self ):
28+ return self .root .previous
29+
30+ def append (self , value ):
31+ if self .maxsize is not None and self .length >= self .maxsize :
32+ raise Exception ('Full' )
33+ node = Node (value )
34+ tailnode = self .tailnode ()
35+ tailnode .next = node
36+ node .next = self .root
37+ node .previous = tailnode
38+ self .root .previous = node
39+ self .length += 1
40+
41+ def append_left (self , value ):
42+ if self .maxsize is not None and self .length >= self .maxsize :
43+ raise Exception ('Full' )
44+ node = Node (value )
45+ headnode = self .headnode ()
46+ self .root .next = node
47+ node .next = headnode
48+ node .previous = self .root
49+ headnode .previous = node
50+ self .length += 1
51+
52+ def __iter__ (self ):
53+ for node in self ._iter_node ():
54+ yield node .value
55+
56+ def _iter_node (self ):
57+ curnode = self .headnode ()
58+ while curnode is not self .root :
59+ yield curnode
60+ curnode = curnode .next
61+
62+ def remove (self , node ):
63+ if node is self .root :
64+ return
65+ prevnode = node .previous
66+ prevnode .next = node .next
67+ node .next .previous = prevnode
68+ value = node .value
69+ del node
70+ self .length -= 1
71+ return value
72+
73+ def reverse_node (self ):
74+ curnode = self .tailnode ()
75+ while curnode is not self .root :
76+ yield curnode
77+ curnode = curnode .previous
78+
79+ def pop (self ):
80+ if self .root .next is self .root :
81+ return
82+ tailnode = self .tailnode ()
83+ prevnode = tailnode .previous
84+ nextnode = tailnode .next
85+ prevnode .next = nextnode
86+ nextnode .previous = prevnode
87+ value = tailnode .value
88+ del tailnode
89+ self .length -= 1
90+ return value
91+
92+ def popleft (self ):
93+ if self .root .next is self .root :
94+ return
95+ headnode = self .headnode ()
96+ prevnode = headnode .previous
97+ nextnode = headnode .next
98+ prevnode .next = nextnode
99+ nextnode .previous = prevnode
100+ value = headnode .value
101+ self .length -= 1
102+ del headnode
103+ return value
104+
105+
106+ def test ():
107+ dll = Circular_Double_LinkedList ()
108+ for i in range (10 ):
109+ dll .append (i )
110+ assert len (dll ) == 10
111+ assert list (dll ) == [i for i in range (10 )]
112+ dll .append_left (- 1 )
113+ assert list (dll ) == [- 1 ] + [i for i in range (10 )]
114+ assert len (dll ) == 11
115+ assert dll .pop () == 9
116+ assert dll .popleft () == - 1
117+ assert len (dll ) == 9
118+
119+
120+ if __name__ == "__main__" :
121+ test ()
0 commit comments