Linked List in Python

About Linked List

Linked List 를 구현하기 전에 간단하게 Linked List 에 대해 정리하고 넘어가자.

Linked List 는 문자 그대로, item 이 물리적으로 연결된 구조를 갖는다. Linked List에 item을 node 라고 부르는데, node는 2개의 field로 이루어져 있다.

1. Data : 값을 저장하고 있다.
2. Next : 다음 node 참조 값을 저장하고 있다.

그림으로 표현하면 아래와 같이 생겼다.

Linked List에서 가장 앞의 node 를 특별하게 head라고 부르는다. 우리는 head를 시작점으로 list를 순회 할 수 있다.

Requirement

내가 제작하려는 Linked List 의 요구사항은 아래와 같다.

• List 를 이용하여 Linked List 를 초기화 할 수 있을 것.
• print() 함수를 사용하여 Linked List 의 모든 Node 를 출력할 수 있을 것.
• Linked List를 iterable 하게 구성할 것.
• Node 를 제일 앞에 추가하는 함수를 구현할 것.
• Node 를 제일 끝에 추가하는 함수를 구현할 것.
• 특정 Node 앞에 새로운 Node 를 추가하는 함수를 구현할 것.
• 특정 Node 뒤에 새로운 Node 를 추가하는 함수를 구현할 것.
• 특정 Node 를 삭제하는 함수를 구현할 것.

Implement

A. 데이터를 저장하는 Node Class를 정의한다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
    
    def __str__(self):
        return str(self.data)

B. Node를 관리하는 LinkedList Class를 정의한다.

class LinkedList:
    pass

C. LinkedList Class에 List를 이용하여 Linked List를 초기화 하는 init() 함수를 구현한다.

def __init__(self, nodes=None):
	self.head = None

    if nodes is None:
    	return
        
    node = Node(nodes[0])
    self.head=node

    nodes.remove(nodes[0])

    for element in nodes:
    	nextNode = Node(element)
        node.next = nextNode
        node = nextNode

List 를 사용하여 LinkedList를 초기화 할수 있는지 확인한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])

node = linkedList.head
while node is not None:
    print(node.data)
    node = node.next

Output:

A
B
C
D
E

D. print()를 손쉽게 하기 위해 str() 함수를 추가한다.

def __str__(self):
	nodes = []
    node = self.head
    while node is not None:
    	nodes.append(str(node.data))
        node = node.next
        
    nodes.append(str(None))
    return ' -> '.join(nodes)

___str__() 함수가 정상적으로 동작하는지 확인한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)

Output:

A -> B -> C -> D -> E -> None

E. LinkedList Class 를 iterable하게 만든다.

iterater 프로토콜을 구현하기 위해 __iter__() 함수를 Generator 로 구현한다.

def __iter__(self):
	node = self.head
    while node is not None:
    	yield node
        node = node.next

LinkedList 가 iterable 하기 때문에 이제 for 문을 사용할 수 있다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])


for element in linkedList:
    print(ele)

Output:

A
B
C
D
E

F. Data를 LinkedList 제일 앞에 추가하는 함수를 구현한다.

def add_first(self, data):
	node = Node(data)
    node.next = self.head
    self.head = node

1. 새로운 Node의 next를 head를 가르키게 한다.
2. head를 새로운 Node로 변경한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.add_first("0")
print(linkedList)

Output

A -> B -> C -> D -> E -> None
0 -> A -> B -> C -> D -> E -> None

G. Data를 LinkedList 제일 끝에 추가하는 함수를 구현한다.

def add_last(self, data):
	newNode = Node(data)

	node = self.head
	while node.next is not None:
		node = node.next
	
	node.next = newNode

1. 맨 마지막 노드(node.next 가 None 인 것)를 찾는다.
2. 마지막 노드에 새로운 Node 를 추가한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.add_last("F")
print(linkedList)

Output

A -> B -> C -> D -> E -> None
A -> B -> C -> D -> E -> F -> None

H. 특정 노드 앞에 Data를 추가하는 함수를 구현한다.

def add_before(self, target, addData):
	newNode = Node(addData)

	node = self.head
	while True:
		if node is None:
			raise Exception('Can not find value: ' + str(addData))

		if node.data == str(target):
			preNode.next = newNode
			newNode.next = node
			break
		preNode = node
		node = node.next

1. node 가 None 이면 Exception을 발생시킨다.
   1-1. node 가 None이라는 건 데이터를 찾지 못한 경우이다.
2. node.data 가 target 과 동일 한지 확인한다.
3. 동일하면,
   3-1. 이전 node.next에 newNode를 추가한다.
   3-2. newNode.next에 현재 node를 추가한다.

target 앞에 추가해야 함으로, 이전 node 정보를 저장하고 있어야 한다.

preNode = node
node = node.next

target을 못 찾는 경우, 에러가 발생하는지 확인한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
linkedList.add_before("F", "0")
print(linkedList)

output

Traceback (most recent call last):
  File "d:\vscode_ws\DataStructure_N_Algorithm\LinkedList.py", line 75, in <module>
    linkedList.add_before("F", "0")
  File "d:\vscode_ws\DataStructure_N_Algorithm\LinkedList.py", line 61, in add_before
    raise Exception('Can not find value: ' + str(addData))
Exception: Can not find value: 0

C 앞에 0을 추가한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])

print(linkedList)
linkedList.add_before("C", "0")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> B -> 0 -> C -> D -> E -> None

I. 특정 노드 뒤에 Data를 추가하는 함수를 구현한다.

def add_after(self, target, addData):
	newNode = Node(addData)

	node = self.head
	while True:            
		if node is None:
			raise Exception('Can not find value: ' + str(target))
		
		if node.data == str(target):
			newNode.next = node.next
			node.next = newNode
			break
		
		node = node.next

1. node 가 None 이면 Exception을 발생시킨다.
   1-1. node 가 None이라는 건 데이터를 찾지 못한 경우이다.
2. node.data 가 target 과 동일 한지 확인한다.
3. 동일하면,
   3-1. newNode.next에 node.next를 연결 시킨다.
   3-2. node.next에 newNode를 연결 시킨다.

C 뒤에 0을 추가한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])

print(linkedList)
linkedList.add_after("C", "0")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> B -> C -> 0 -> D -> E -> None

J. 특정 노드를 삭제하는 함수를 구현한다.

def remove(self, target):
	
	if self.head.data == str(target):
		self.head = self.head.next
		return

	node = self.head

	while True:
		if node is None:
			raise Exception('Can not find value: ' + str(target))
		
		if node.data == str(target):
			preNode.next = node.next
			del node
			break

		preNode = node
		node = node.next

1. head.data 와 target 동일하다면,
   1-1. head가 head.next를 가르키게 한다.
2. head.data 와 target 다르면,
   2-1. 순회하면서 target 같은 값을 가진 Node를 찾는다.
3. node.data 가 target 과 동일하면
   3-1. 이전 node.next에 현재 node.next를 연결시킨다.
   3-2. 현재 node를 삭제한다.

head 값, 제일 앞에 있는 값을 삭제한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.remove("A")
print(linkedList)

output

A -> B -> C -> D -> E -> None
B -> C -> D -> E -> None

중간 값을 삭제한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.remove("B")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> C -> D -> E -> None

마지막 값을 삭제한다.

linkedList = LinkedList(["A", "B", "C", "D", "E"])
print(linkedList)
linkedList.remove("E")
print(linkedList)

output

A -> B -> C -> D -> E -> None
A -> B -> C -> D -> None

Reference

Linked Lists in Python: An Introduction