[자료구조] 연결 리스트 (Linked list) 개념과 구현

#1. 연결 리스트 (Linked list)

 

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

 

연결리스트는 말 그대로 데이터를 저장하고 있는 노드를 서로 연결하여 구현한 하나의 자료구조이다.

일반적인 배열은 크기가 정해져 있어서 새로운 데이터를 추가하는데 있어 메모리 공간 활용이 비효율적이다.

이에 반해 연결리스트는 노드만 추가해주면 되기 때문에 메모리 관리면에서 좀 더 효율적이라고 볼 수 있다.

 

연결리스트 = ["첫번째노드"] -> ["두번째노드"] -> ["세번째노드"] -> ["마지막노드"]

단순한 연결리스트는 위와 같은 형태를 가지고 있으며 모든 노드는 공통적으로 데이터와 다음 노드의 위치정보를 포함한다.

 

---

#2. 연결 리스트 (Linked list) 구현

 

먼저, 각 노드 객체를 정의하기 위해 노드 Class를 다음과 같이 생성한다.

 

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

클래스 생성자(Constructor)로 데이터(data)와 다음 노드의 정보(next)를 설정한다.

 

개별적인 노드 객체를 생성한 후 next에 할당하면 연결이 되지만, 여러 데이터를 처리하기 위한 연결리스트 Class를 다음과 같이 정의해준다.

 

class LinkedList:
    def __init__(self, value):
        self.head = Node(value) # 시작 노드를 저장
        
# 노드 확인
linked_list1 = LinkedList('first')
print('linked_list1 객체의 head는?:', linked_list1.head.data)

""" linked_list1 객체의 head는?: first """

---

#3. 노드 삽입 메서드 추가 (append)

기존 배열의 쓰이는 메서드처럼 연결리스트 마지막에 새로운 노드를 붙이는 append 메서드를 추가하였다.

마지막 node의 next는 None값을 가지고 있기 때문에 이를 활용해 탐색이 가능하다.

def append(self, value):        # LinkedList 가장 끝에 있는 노드에 새로운 노드 연결
    cur = self.head
    while cur.next is not None: # cur.next = None 이 될 때까지 cur(self.head)의 자리를 while문을 통해 옮겨준다.
        cur = cur.next
    cur.next = Node(value)

---

#4. 모든 노드의 데이터 출력 메서드 추가 (print_all)

append와 비슷하게 현재 커서의 위치를 한칸씩 계속 옮기면서 None값을 찾기까지 탐색한다.

def print_all(self):            
    cur = self.head
    while cur is not None:
        print(cur.data)
        cur = cur.next
 
# 노드 추가
linked_list1.append('second')
linked_list1.append('third')
linked_list1.append('forth')
linked_list1.append('fifth')

# 전체 노드 데이터 출력
linked_list1.print_all()

"""
first
second
third
forth
fifth
"""

---

#5. index번째 노드를 얻기 위한 메서드 추가 (get_node)

count 변수를 통해 옆 노드로 이동한 횟수와 매개변수로 받은 index 값을 비교해 특정 index의 노드를 가져온다.

def get_node(self, index):
    cur = self.head
    cnt = 0
    while cnt < index:
        cur = cur.next
        cnt += 1
    return cur

# 특정 노드 추출
node = linked_list1.get_node(3)
print('3번째 index의 노드는?: ', node.data)

"""3번째 index의 노드는?:  forth"""

---

#6. 특정 index에 노드 추가를 위한 메서드 추가 (add_node)

구현이 조금 번거롭다.
넣으려고 하는 인덱스의 전 노드와 이것의 옆 노드사이에 새 노드를 추가하고 연결한다.

변수 index가 0이 들어왔을 때 새로운 노드가 head값이 되는 것을 주의하면 된다. 

참고로 없는 노드를 패스하고 연결을 하진 못한다.
(예를 들어 마지막 노드 인덱스가 4인데 5를 건너 뛰고 6에 삽입을 못한다. )

def add_node(self, index, value):
    new_node = Node(value)
    if index == 0:                  # index가 0인 경우 새로운 노드의 next로 head노드(원래 첫번째 노드)를 지정해준다.
        new_node.next = self.head   # 이후 새 노드가 head가 되면 index 첫번째 노드 치환 완료
        self.head = new_node

    cur = self.get_node(index - 1)
    next_node = cur.next
    cur.next = new_node
    new_node.next = next_node
    
# 특정 인덱스에 노드 추가
linked_list1.add_node(5, 'new_node')
new_node = linked_list1.get_node(5)
print('새로운 노드는?: ', new_node.data)

"""새로운 노드는?:  new_node"""

---

#7. 특정 index 노드를 삭제하는 메서드 추가 (delete_node)

특정 인덱스 바로 앞의 노드에 특정 인덱스 노드 다음 노드를 강제로 연결한다.

특정 인덱스 노드가 연결이 되지 않는다. 

def delete_node(self, index):
    if index == 0:
        self.head.next = self.head  # index가 0이면 head 다음 노드가 head로 치환한다.
        return
    cur = self.get_node(index - 1)
    cur.next = cur.next.next
    
# 특정 인덱스 노드 제거
linked_list1.delete_node(5)	# 'new_node'를 삭제한다.
linked_list1.print_all()
"""
first
second
third
forth
fifth
"""

---