Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Linked List implementation in Python2/3
# coding: utf-8
from __future__ import print_function
import sys
try:
from collections.abc import MutableSequence
except ImportError:
from collections import MutableSequence
try:
range = xrange
except NameError:
pass
class Record(object):
def __init__(self, value, next=None):
self.value = value
self.next = next
def __repr__(self):
return "Record({})".format(repr(self.value))
class LL(MutableSequence):
def __init__(self, values=None):
if isinstance(values, int):
values = range(values)
if values:
self._populate(values)
else:
self.head = None
self.length = 0
def _populate(self, values):
item = self.head = Record(values[0])
for i in range(1, len(values)):
item.next = Record(values[i])
item = item.next
self.length = len(values)
def _getrecord(self, index):
if index < 0:
index = len(self) + index
for i, item in enumerate(self._record_iter()):
if i == index:
return item
raise IndexError
def __getitem__(self, index):
return self._getrecord(index).value
def __setitem__(self, index, value):
self._getrecord(index).value = value
def __delitem__(self, index):
if index == 0:
if self.head is None:
raise IndexError
self.head = self.head.next
self.length -= 1
return
item = self._getrecord(index-1)
if item.next is None:
raise IndexError
item.next = item.next.next
self.length -= 1
def _insert_at_start(self, value):
new_head = Record(value)
new_head.next = self.head
self.head = new_head
self.length += 1
return None
def insert(self, index, value):
if index == 0:
return self._insert_at_start(value)
try:
item = self._getrecord(index)
except IndexError:
if index < 0:
return self._insert_at_start(value)
item = self._getrecord(-1)
new_item = Record(value)
new_item.next = item.next
item.next = new_item
self.length += 1
return None
def _record_iter(self):
if self.head is None:
return
item = self.head
yield item
while item.next:
item = item.next
yield item
def __iter__(self):
for item in self._record_iter():
yield item.value
def __len__(self):
# return sum(1 for item in self)
return self.length
def __repr__(self):
return "LL([{}])".format(", ".join(repr(item.value) for item in self._record_iter()))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment