Removing duplicates from a linked list without a buffer

I am practicing a problem in "Cracking the Coding Interview". The problem is to remove duplicates in a linked list without the use of a buffer. I interpreted this as not using a list or any large data structure such as a hash to store unique nodes.

My algorithm is inefficient I think. It iterates an anchor across the linked list. From that anchor, a second sub-iteration occurs which removes any nodes that is the same as the anchor. Thus, there are a total of two loops. I think the time complexity is either O(n^2) or O(nlogn)

Any better algorithms are welcome. Since I am a novice in Python, please give me suggestions on my coding style.

```
class Node(object):

def __init__(self, data):
self.data = data
self.next = None

def getData(self):
return self.data

def setNext(self, node):
self.next = node

def getNext(self):
return self.next

class LinkedList(object):

def __init__(self, dataList):
assert len(dataList) > 0
self.head = Node(dataList[0])
iterNode = self.head

for i in range(1, len(dataList)):
iterNode.setNext(Node(dataList[i]))
iterNode = iterNode.getNext()
iterNode.setNext(None)

def printList(self):
iterNode = self.head

while iterNode is not None:
print(iterNode.getData())
iterNode = iterNode.getNext()

def removeDuplicates(self):
assert self.head is not None
anchor = self.head

while anchor is not None:
iterator = anchor
while iterator is not None:
prev = iterator
iterator = iterator.getNext()
if iterator is None:
break
if iterator.getData() == anchor.getData():
next = iterator.getNext()
prev.setNext(next)

anchor = anchor.getNext()

dataList = ["hello", "world", "people", "hello", "hi", "hi"]

linkedL

-
Problem statement

The problem is underdefined. In a real-life interview I'd ask immediately, do we care about the stability? If yes, your solution is good. If no, sort the list first.

-
Complexity

\$O(n^2)\$ and \$O(n\log n)\$ are quite different beasts. This algorithm is \$O(n^2)\$ obviously. If sorting is allowed, there is a \$O(n \log n)\$ solution.

-
getters and setters

Python doesn't have a concept of public and private. At the end of the day everything is public. getData, getNext and setNext do not serve any purpose but generating entropy.

Even in the language which encourages such approach it only makes sense when there is an invariant to maintain. Unrestricted getter and setter are as good as a public member.

StackExchange Code Review Q#116945, answer score: 4