🚀 들어가기
링크드 리스트라는 자료구조를 배우면서 첫번째로 겪었던 고비였습니다... C언어 포인터의 개념도 잘 잡혀있지 않았던터라 여기 연결되고 저기 연결되는 링크드 리스트라는 자료구조가 어려웠던 것 같습니다.
그럼에도 노드 하나를 삭제하고 다른 노드로 연결시키는 과정을 그려가면서 이해하니 어느정도 머리에 들어왔던 경험이 있습니다. 시간이 지나 링크드 리스트를 다시 만났을 때 이전의 두려움보다는 반가움이 더 컸네요.
✨ 링크드 리스트
💡 개념
링크드 리스트(Linked List)는 연결 리스트라고도 하는데요, 데이터들이 나열된 자료구조라고 이해하면 쉽습니다.
배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조라면, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 연결해서 관리하는 데이터 구조입니다.
링크드 리스트의 데이터는 노드(Ndoe)라고 불립니다.
노드와 노드가 연결된 데이터 구조가 링크드 리스트인 것이죠. 또 노드는 데이터 값과 포인터(Pointer)로 구성되어 있습니다.
포인터는 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간입니다.
링크드 리스트는 미리 데이터 공간을 할당하지 않아도 된다는 장점이 있습니다. 동적으로 길이가 조정된다는 것이죠. 하지만 연결을 위해서 추가적인 데이터 공간(포인터)가 필요하므로 저장공간이 비효율적이긴 합니다. 또 데이터 추가 및 삭제의 구현이 번거로운 단점이 있습니다.
링크드 리스트의 구조와 여러 동작들을 그림으로 설명해보겠습니다.
📗 설명
⏺️ 링크드 리스트의 구조
링크드 리스트의 구조입니다.
일반적인 노드는 데이터 값과 포인터 공간을 갖고 있습니다.
위와 같은 노드가 연결되면 링크드 리스트가 됩니다.
⏺️ 링크드 리스트의 탐색
다음은 링크드 리스트의 동작을 알아보겠습니다. 먼저 알아볼 동작은 탐색입니다.
링크드 리스트에서 탐색은 단순합니다. 시작 노드에서부터 탐색을 시작하여 포인터를 통해 노드를 이동하며 탐색하고자 하는 값을 확인하면 됩니다.
다음 그림에서 노드 C를 탐색해보겠습니다.
먼저 시작 노드를 현재 노드로 설정하고 데이터 값을 확인합니다. 원하는 값이 아닐 경우 현재 노드의 포인터가 가리키는 노드를 현재 노드로 변경합니다. 단순하게 이동한다고 이해해도 됩니다.
다음과 같이 순서대로 이동하면 탐색하고자 했던 노드 C를 찾을 수 있습니다.
⏺️ 링크드 리스트의 삽입
다음 알아볼 동작은 삽입입니다.
데이터 구조의 맨 앞 혹은 맨 뒤에서 삽입 및 삭제가 이뤄졌던 스택과 큐와는 달리 링크드 리스트는 중간에서 삽입 및 삭제가 가능하기 때문에 동작을 이해하는데 약간의 어려움이 있습니다.
삽입 동작은 크게 세가지로 나눠 이해할 수 있습니다.
- 맨 앞에 삽입
- 맨 뒤에 삽입
- 특정 노드 뒤에 삽입
맨 앞 삽입
첫번째로 데이터 구조의 맨 앞에 삽입하는 경우입니다.
노드 A, B, C가 연결된 상태에서 노드 D를 맨 앞에 삽입하고 싶은 상황입니다.
먼저 노드 D의 포인터가 시작 노드인 노드 A를 가리키게 합니다. 그 다음 시작 노드를 노드 D로 만들면 삽입 동작이 완료됩니다.
맨 뒤 삽입
두번째로 데이터 구조의 맨 뒤에 삽입하는 경우입니다. 이 경우는 특정 노드가 아닌 링크드 리스트의 마지막에 추가하는 경우입니다.
노드 A, B, C가 연결된 상태에서 노드 D를 맨 뒤에 삽입하고 싶은 상황입니다.
먼저 현재 링크드 리스트의 마지막 노드를 찾아갸야 합니다. 현재 노드를 시작 노드로 설정합니다. 그 후 현재 노드의 다음 노드가 존재하지 않을 때까지 포인터를 통해 다음 노드로 이동합니다.
현재 노드의 다음 노드가 없다면(노드 C) 현재 노드의 포인터가 추가하려는 노드 D를 가리키도록 하면 동작이 완료됩니다.
특정 노드 뒤 삽입
마지막으로 특정 노드 뒤에 삽입하는 경우입니다.
노드 A, B, C가 연결된 상태에서 노드 D를 노드 B와 바로 뒤에 연결하고 싶은 상황입니다.
먼저 삽입하고자 하는 위치인 노드 B까지 이동해야 합니다. 현재 노드를 시작 노드로 설정하여 현재 노드가 노드 B가 될 때까지 포인터를 통해 이동합니다.
현재 노드가 노드 B가 되었다면 노드 B의 다음 노드인 노드 C를 노드 D가 가리키게 합니다. 그 후 노드 B의 포인터가 노드 D를 가리키게 하면 노드 D의 삽입이 완료됩니다.
⏺️ 링크드 리스트의 삭제
다음 알아볼 동작은 삭제입니다. 삭제 또한 삽입과 같이 세가지로 구분할 수 있습니다.
- 맨 앞 노드 삭제
- 맨 뒤 노드 삭제
- 특정 노드 삭제
맨 앞 노드 삭제
첫번째로 맨 앞 노드 삭제입니다. 시작 노드인 노드 A를 삭제하려는 상황입니다.
먼저 현재 노드를 시작 노드로 설정합니다. 그 후 시작 노드의 다음 노드를 시작 노드로 설정하고 현재 노드를 삭제하면 동작이 완료됩니다.
맨 뒤 노드 삭제
두번째는 맨 뒤 노드 삭제입니다. 마지막 노드인 노드 D를 삭제하려는 상황입니다.
먼저 현재 노드를 시작 노드로 설정합니다. 그 후 다음 노드의 포인터가 가리키는 노드가 없을 때까지 노드를 이동합니다.
현재 노드(노드 C)의 다음 노드(노드 D)가 가리키는 노드가 없을 때 현재 노드의 포인터가 가리키는 값을 없애고 현재 노드의 다음 노드를 삭제합니다. 이상으로 동작이 완료됩니다.
특정 노드 삭제
마지막은 특정 노드 삭제입니다. 특정 노드 삭제의 경우 특정 노드가 시작 노드인 경우, 마지막 노드인 경우, 중간에 있는 노드인 경우로 다시 나눌 수 있습니다. 특정 노드는 데이터 값으로 지정한다고 가정하겠습니다.
| 먼저 특정 노드가 시작 노드인 경우입니다. 노드 A를 삭제하려고 합니다.
현재 노드를 시작 노드로 설정한 후 데이터 값을 특정 노드의 데이터 값과 비교합니다. 특정 노드의 데이터 값이 시작 노드와 같다면 시작 노드를 삭제한 방식으로 진행합니다.
| 다음은 특정 노드가 중간에 있는 노드인 경우입니다. 노드 C를 삭제하려고 합니다.
현재 노드를 시작 노드로 설정한 후 현재 노드의 다음 노드의 데이터 값이 특정 노드의 데이터 값과 같을 때까지 노드를 이동합니다.
현재 노드의 다음 노드의 데이터 값과 특정 노드의 데이터 값이 같다면 현재 노드(노드 B)의 포인터가 다음 노드(노드 C)의 다음 노드(노드 D)를 가리키도록 합니다. 그 후 다음 노드(노드 C)를 삭제하면 동작이 완료됩니다.
| 다음은 특정 노드가 마지막 노드인 경우입니다. 노드 D를 삭제하려고 합니다.
현재 노드의 다음 노드의 데이터 값과 특정 노드의 데이터 값이 같을 때까지 노드를 이동한다는 것은 이전 경우와 동일합니다.
이전 경우와의 차이점은 다음 노드(노드 D)의 포인터가 가리키는 노드가 없다는 것입니다. 다음 노드의 포인터가 가리키는 노드가 없다면 현재 노드(노드 C)의 포인터가 가리키는 값을 없애고 다음 노드(노드 D)를 삭제합니다. 이상으로 삭제 동작이 완료됩니다.
📝 파이썬으로 구현
파이썬에서 링크드 리스트의 기능은 일반 리스트를 사용하면 됩니다. 다음은 직접 구현입니다.
링크드 리스트는 노드로 연결되어 있기 때문에 노드(Node)를 먼저 정의해야 합니다.
class Node:
def __init__(self,data,next=None):
self.data = data
self.next = next
node = Node(3)
print(node.data) # 3다음은 노드들을 연결 시키는 링크드 리스트의 구현입니다.
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class Linked_List:
def __init__(self, data):
self.head = Node(data)
def show(self):
# 전체 노드 출력력
current_node = self.head
while current_node:
print(current_node.data,end=" ")
current_node = current_node.next
def search(self, data):
# 특정 노드 탐색
current_node = self.head
while current_node:
if current_node.data == data:
return True
current_node = current_node.next
return False
def add(self, data):
# 맨 뒤에 추가
current_node = self.head
while current_node.next:
current_node = current_node.next
current_node.next = Node(data)
def insert(self, target, data):
# 특정 노드 뒤에 추가
current_node = self.head
target_node = None
while current_node:
if current_node.data == target:
target_node = current_node
break
current_node = current_node.next
if target_node == None:
print("해당 노드가 없습니다.")
return
else:
insert_node = Node(data)
insert_node.next = target_node.next
target_node.next = insert_node
def insertHead(self, data):
#맨 앞에 추가
current_node = self.head
insert_node = Node(data)
insert_node.next = current_node
self.head = insert_node
def deleteHead(self):
#맨 앞 노드 삭제
current_node = self.head
if current_node.next != None:
next_node = current_node.next
self.head = next_node
del current_node
return
else:
print("노드가 하나일 때 삭제할 수 없습니다.")
def deleteTail(self):
#맨 뒤 노드 삭제
current_node = self.head
if current_node.next == None:
print("노드가 하나일 때 삭제할 수 없습니다.")
while current_node.next:
if current_node.next.next == None:
next_node = current_node.next
current_node.next = None
del next_node
return
current_node = current_node.next
return
def delete(self,target):
#특정 노드 삭제
current_node = self.head
if current_node.data == target:
# 맨 앞 노드일 때
next_node = current_node.next
self.head = next_node
del current_node
return
while current_node.next:
if current_node.next.data == target:
if current_node.next.next:
# 중간 노드일 때
delete_node = current_node.next
current_node.next = current_node.next.next
del delete_node
return
else:
# 맨 뒤 노드일 때
delete_node = current_node.next
current_node.next = None
del delete_node
return
current_node = current_node.next
print("해당 노드를 찾을 수 없습니다.")
linked_list = Linked_List(1)
num_arr = [2,3,4,5]
for num in num_arr:
linked_list.add(num)
linked_list.show() # 1 2 3 4 5
if linked_list.search(6):
print("해당 노드가 있습니다.")
else:
print("해당 노드가 없습니다.")
linked_list.insert(5,6)
linked_list.show() # 1 2 3 4 5 6
linked_list.insertHead(0)
linked_list.show() # 0 1 2 3 4 5 6
linked_list.deleteHead()
linked_list.show() # 1 2 3 4 5 6
linked_list.delete(5)
linked_list.show() # 1 2 3 4 6
linked_list.deleteTail()
linked_list.show() # 1 2 3 4
linked_list.delete(1)
linked_list.show() # 2 3 4
linked_list.delete(4)
linked_list.show() # 2 3🎁 관련 문제
