1+ class Node :
2+ def __init__ (self ,data ):
3+ self .data = data
4+ self .next = None
5+ self .prev = None
6+
7+
8+ class CircularDoublyLinkedList :
9+ def __init__ (self ):
10+ self .first = None
11+
12+ def get_node (self ,index ):
13+ current = self .first
14+ for i in range (index ):
15+ current = current .next
16+ if current == self .first :
17+ return None
18+ return current
19+
20+ def insert_after (self ,ref_node ,new_node ):
21+ new_node .prev = ref_node
22+ new_node .next = ref_node .next
23+ new_node .next .prev = new_node
24+ ref_node .next = new_node
25+
26+ def insert_before (self ,ref_node ,new_node ):
27+ self .insert_after (ref_node .prev ,new_node )
28+
29+ def insert_at_end (self ,new_node ):
30+ if self .first is None :
31+ self .first = new_node
32+ new_node .next = new_node
33+ new_node .prev = new_node
34+ else :
35+ self .insert_after (self .first .prev ,new_node )
36+
37+ def insert_at_beg (self ,new_node ):
38+ self .insert_at_end (new_node )
39+ self .first = new_node
40+
41+ def remove (self ,node ):
42+ if self .first .next == self .first :
43+ self .first = None
44+ else :
45+ node .prev .next = node .next
46+ node .next .prev = node .prev
47+ if self .first == node :
48+ self .first = node .next
49+
50+ def display (self ):
51+ if self .first is None :
52+ return
53+ current = self .first
54+ while True :
55+ print (current .data ,end = ' ' )
56+ current = current .next
57+ if current == self .first :
58+ break
59+
60+
61+ a_cdllist = CircularDoublyLinkedList ()
62+
63+ print ('Menu' )
64+ print ('insert <data> after <index>' )
65+ print ('insert <data> before <index>' )
66+ print ('insert <data> at beg' )
67+ print ('insert <data> at end' )
68+ print ('remove <index>' )
69+ print ('quit' )
70+
71+ while True :
72+ print ('The list: ' ,end = '' )
73+ a_cdllist .display ()
74+ print ()
75+ do = input ('What would you like to do? ' ).split ()
76+
77+ operation = do [0 ].strip ().lower ()
78+
79+ if operation == 'insert' :
80+ data = int (do [1 ])
81+ position = do [3 ].strip ().lower ()
82+ new_node = Node (data )
83+ suboperation = do [2 ].strip ().lower ()
84+ if suboperation == 'at' :
85+ if position == 'beg' :
86+ a_cdllist .insert_at_beg (new_node )
87+ elif position == 'end' :
88+ a_cdllist .insert_at_end (new_node )
89+ else :
90+ index = int (position )
91+ ref_node = a_cdllist .get_node (index )
92+ if ref_node is None :
93+ print ('No such index.' )
94+ continue
95+ if suboperation == 'after' :
96+ a_cdllist .insert_after (ref_node ,new_node )
97+ elif suboperation == 'before' :
98+ a_cdllist .insert_before (ref_node ,new_node )
99+
100+ elif operation == 'remove' :
101+ index = int (do [1 ])
102+ node = a_cdllist .get_node (index )
103+ if node is None :
104+ print ('No such index.' )
105+ continue
106+ a_cdllist .remove (node )
107+
108+ elif operation == 'quit' :
109+ break