Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
Linked List implementation in Python2/3
# coding: utf-8
from __future__ import print_function
import sys
from import MutableSequence
except ImportError:
from collections import MutableSequence
range = xrange
except NameError:
class Record(object):
def __init__(self, value, next=None):
self.value = value = 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.head = None
self.length = 0
def _populate(self, values):
item = self.head = Record(values[0])
for i in range(1, len(values)): = Record(values[i])
item =
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.length -= 1
item = self._getrecord(index-1)
if is None:
raise IndexError =
self.length -= 1
def _insert_at_start(self, value):
new_head = Record(value) = 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)
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
self.length += 1
return None
def _record_iter(self):
if self.head is None:
item = self.head
yield item
item =
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