. Also on the plus side, these are better abstracted - that is, they fit some specific purposes well and don't allow things that may be best avoided.
All 3 modules are thoroughly unit tested; pass pylint; and run on CPython 2.7, CPython 3.6, Pypy 5.10.0, Pypy3 5.10.0 and Jython 2.7.
Linked_list allows:
Operation |
Time in Big O notation: Linked list |
Time in Big O notation: Builtin list |
Time in Big O notation: collections.deque |
append |
O(1) |
O(1) (amortized) |
O(1) |
| prepend | O(1) | O(n) | O(1) |
| deletion from beginning | O(1) | O(n) | O(1) |
| delete by value | O(n) | O(n) | O(n) |
| length of list | O(1) | O(1) | O(1) |
| list reversal | O(n) | O(n) | O(n) |
| membership test | O(n) | O(n) | O(n) |
You can obtain the code here.
Interestingly, I modified count to use this class instead of a builtin Python list, and it was both slower and used more RSS (memory). I suppose there's a reason why people don't use linked lists in Python.
Also, collections.deque makes the LIFO and FIFO less interesting.
But at least all this was fun to write . Also on the plus side, these are better abstracted - that is, they fit some specific purposes well and don't allow things that may be best avoided.
Example use:
In [1]: import linked_list_mod
In [2]: file_ = open('/etc/protocols', 'r')
In [3]: linked_list = linked_list_mod.Linked_list(line.rstrip() for line in file_)
In [4]: linked_list.append(':)')
In [5]: file_.close()
In [6]: for element in linked_list:
...: print(element)
...:
# Internet (IP) protocols
#
# Updated from http://www.iana.org/assignments/protocol-numbers and other
# sources.
# New protocols will be added on request if they have been officially
# assigned by IANA and are not historical.
# If you need a huge list of used numbers please install the nmap package.
ip 0 IP # internet protocol, pseudo protocol number
#hopopt 0 HOPOPT # IPv6 Hop-by-Hop Option [RFC1883]
icmp 1 ICMP # internet control message protocol
igmp 2 IGMP # Internet Group Management
ggp 3 GGP # gateway-gateway protocol
ipencap 4 IP-ENCAP # IP encapsulated in IP (officially ``IP'')
st 5 ST # ST datagram mode
tcp 6 TCP # transmission control protocol
egp 8 EGP # exterior gateway protocol
igp 9 IGP # any private interior gateway (Cisco)
pup 12 PUP # PARC universal packet protocol
udp 17 UDP # user datagram protocol
hmp 20 HMP # host monitoring protocol
xns-idp 22 XNS-IDP # Xerox NS IDP
rdp 27 RDP # "reliable datagram" protocol
iso-tp4 29 ISO-TP4 # ISO Transport Protocol class 4 [RFC905]
dccp 33 DCCP # Datagram Congestion Control Prot. [RFC4340]
xtp 36 XTP # Xpress Transfer Protocol
ddp 37 DDP # Datagram Delivery Protocol
idpr-cmtp 38 IDPR-CMTP # IDPR Control Message Transport
ipv6 41 IPv6 # Internet Protocol, version 6
ipv6-route 43 IPv6-Route # Routing Header for IPv6
ipv6-frag 44 IPv6-Frag # Fragment Header for IPv6
idrp 45 IDRP # Inter-Domain Routing Protocol
rsvp 46 RSVP # Reservation Protocol
gre 47 GRE # General Routing Encapsulation
esp 50 IPSEC-ESP # Encap Security Payload [RFC2406]
ah 51 IPSEC-AH # Authentication Header [RFC2402]
skip 57 SKIP # SKIP
ipv6-icmp 58 IPv6-ICMP # ICMP for IPv6
ipv6-nonxt 59 IPv6-NoNxt # No Next Header for IPv6
ipv6-opts 60 IPv6-Opts # Destination Options for IPv6
rspf 73 RSPF CPHB # Radio Shortest Path First (officially CPHB)
vmtp 81 VMTP # Versatile Message Transport
eigrp 88 EIGRP # Enhanced Interior Routing Protocol (Cisco)
ospf 89 OSPFIGP # Open Shortest Path First IGP
ax.25 93 AX.25 # AX.25 frames
ipip 94 IPIP # IP-within-IP Encapsulation Protocol
etherip 97 ETHERIP # Ethernet-within-IP Encapsulation [RFC3378]
encap 98 ENCAP # Yet Another IP encapsulation [RFC1241]
# 99 # any private encryption scheme
pim 103 PIM # Protocol Independent Multicast
ipcomp 108 IPCOMP # IP Payload Compression Protocol
vrrp 112 VRRP # Virtual Router Redundancy Protocol [RFC5798]
l2tp 115 L2TP # Layer Two Tunneling Protocol [RFC2661]
isis 124 ISIS # IS-IS over IPv4
sctp 132 SCTP # Stream Control Transmission Protocol
fc 133 FC # Fibre Channel
mobility-header 135 Mobility-Header # Mobility Support for IPv6 [RFC3775]
udplite 136 UDPLite # UDP-Lite [RFC3828]
mpls-in-ip 137 MPLS-in-IP # MPLS-in-IP [RFC4023]
manet 138 # MANET Protocols [RFC5498]
hip 139 HIP # Host Identity Protocol
shim6 140 Shim6 # Shim6 Protocol [RFC5533]
wesp 141 WESP # Wrapped Encapsulating Security Payload
rohc 142 ROHC # Robust Header Compression
:)
See also this list of datastructures I've worked on.
You can e-mail the author with questions or comments:
