자료구조 - 단일 연결리스트

자료구조는 컴퓨터에서 데이터를 효율적으로 저장, 관리, 수정하기 위한 논리적 구조이다.

문제해결의 목적과 데이터 특성에 맞는 최적의 자료구조를 선택하는 것이 중요하다.

 

자료구조는 크게 선형과 비선형으로 나누어져 있다.

• 선형 자료구조: 데이터가 순차적으로 나열된 구조이다.
• 비선형 자료구조 : 데이터가 계층적 또는 네트워크 형태로 연결된 구조이다.

저번에는 선형 자료구조에서 배열, 스택, 큐를 살펴보았다. 이번에는 연결리스트를 알아보자!

 

---

연결리스트(linked list)

1. 데이터 요소를 연결된 노드로 표현하는 방식이다. -> 떨어진 곳에 존재하는 데이터를 화살표호 연결해서 관리
2. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다.
3. 포인터를 통해 다음 노드로 이동하면서 데이터를 순차적으로 접근할 수 있다.
4. 동적으로 크기 조절될 수 있으며, 데이터의 삽입과 삭제가 빠르게 이루어진다.

 

단일 연결리스트

• 노드(Node) : 연결 리스트의 기본 구성요소로 데이터와 다음 노드를 가리키는 포인터로 구성된다.
• 헤드(Head) : 첫번째 노드를 가리키는 포인터이다.
• 데이터(Data) : 각 노드가 저장하는 값 또는 객체이다.
• 포인터(Pointer) : 노드를 연결한다. 각 노드는 다음 노드를 가리키는 주소를 가지고 있다.
• 테일(Tail) : 연결리스트에서 가장 마지막 노드이다. 이 노드의 포인터는 Null을 가리킨다.

 

연결리스트 데이터 추가(삽입)

A - B 연결리스트에 새로운 C노드를 추가

1. 일단 A노드의 포인터는 B노드를 가리키고 있다.
2. 여기서 C노드를 추가한다면
3. A노드의 next 포인터 값을 C노드의 next 포인터에 넣는다
4. 이후 A노드의 next 포인터가 C노드를 가리키게 한다.
5. A - C - B 순으로 연결되게 된다.

 

연결리스트 데이터 삭제

A - C - B 연결리스트에서 C 노드를 삭제

1. 삭제할 C노드의 앞 노드를 찾는다. (A노드)
2. A노드에 삭제할 C 노드의 next 포인터 값을 저장한다. (이때 A와 C 둘 다 B노드를 가리키고 있는 상태가 된다)
3. 삭제할 C노드의 메모리를 해제한다. 
4. C노드를 가리키는 앞 노드가 없어 논리적으로 삭제된 노드가 된다.

 

연결리스트 데이터 조회

1. 헤드 노드부터 시작한다.
2. 헤드 노드 부터 특정 값이랑 같은지 아닌지를 확인한다.
3. 아니라면 다음 노드로 넘어가고, 맞다면 그 값을 반환한다.
4. 검색하고자 하는 노드가 존재하지 않거나 빈 리스트인 경우를 고려해야 한다.

 

코드 구현

 

연결리스트 중간 삽입

class Node:
    def __init__(self, data):
        self.data = data  # 데이터 담는 저장공간
        self.next = None  # 다음 노드를 가리키는 포인터


class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드를 가리킴

    def insert_after(self, target_data, new_data):	# 리스트 중간 삽입
        current = self.head
        
        # 삽입할 기준 노드 찾기
        while current is not None and current.data != target_data:
            current = current.next
            
        if current is None:
            print(f"기준이 되는 데이터({target_data})가 리스트에 없습니다.")
            return False

        # 새 노드 생성 후 링크 연결하기
        new_node = Node(new_data)
        new_node.next = current.next  # 1단계: 새 노드가 기존 다음 노드를 가리키게 함
        current.next = new_node       # 2단계: 기준 노드가 새 노드를 가리키게 함
        print(f"{target_data} 뒤에 {new_data} 삽입 완료")
        return True

    # 리스트 전체 출력용 함수
    def print_list(self):
        current = self.head
        nodes = []
        while current:
            nodes.append(str(current.data))
            current = current.next
        print(" -> ".join(nodes) if nodes else "비어 있음")



sll = SinglyLinkedList()

# 새 리스트 생성(10 -> 20 -> 30)
sll.head = Node(10)
sll.head.next = Node(20)
sll.head.next.next = Node(30)

print("원래 리스트:")
sll.print_list()  # 10 -> 20 -> 30
print("-" * 30)

# 연결리스트 삽입 (20 뒤에 25 삽입)
sll.insert_after(20, 25)
sll.print_list()  # 10 -> 20 -> 25 -> 30
print("-" * 30)

 

연결리스트 삭제

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # 다음 노드를 가리키는 포인터


class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드를 가리킴

    def delete_after(self, target_data):
        current = self.head
        
        # 삭제할 노드의 '앞 노드' 찾기
        while current is not None and current.data != target_data:
            current = current.next
            
        if current is None or current.next is None:
            print(f"기준 노드가 없거나, {target_data} 뒤에 삭제할 노드가 없습니다.")
            return False

        # 링크를 건너뛰어 삭제하기
        delete_node = current.next         # 삭제될 노드 잠시 보관
        current.next = delete_node.next   # 기준 노드가 삭제될 노드의 다음 노드를 가리키게 함
        print(f"{target_data} 뒤의 데이터({delete_node.data}) 삭제 완료")
        return True

    # 리스트 전체 출력용 함수
    def print_list(self):
        current = self.head
        nodes = []
        while current:
            nodes.append(str(current.data))
            current = current.next
        print(" -> ".join(nodes) if nodes else "비어 있음")



sll = SinglyLinkedList()

# 새 리스트 생성(10 -> 20 -> 30)
sll.head = Node(10)
sll.head.next = Node(20)
sll.head.next.next = Node(30)

print("원래 리스트:")
sll.print_list()  # 10 -> 20 -> 30
print("-" * 30)

# 연결리스트 삭제 (20 뒤의 데이터인 25 삭제)
sll.delete_after(20)
sll.print_list()  # 10 -> 20 -> 30

 

연결리스트 조회

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None  # 다음 노드를 가리키는 포인터


class SinglyLinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드를 가리킴

    # --- 1. 조회 (Search) ---
    def search(self, target_data):
        current = self.head	# head에서 탐색 시작
        position = 0		# 몇 번째인지 세는 카운터
        
        while current is not None:	# 노드가 끝날 때까지 반복
            if current.data == target_data:
                return position 	# 데이터의 인덱스(위치) 반환
            current = current.next	# 다음 노드로 이동
            position += 1
            
        return -1  # 찾지 못했을 경우 -1 반환

    # 리스트 전체 출력용 함수
    def print_list(self):
        current = self.head
        nodes = []
        while current:
            nodes.append(str(current.data))
            current = current.next
        print(" -> ".join(nodes) if nodes else "비어 있음")



sll = SinglyLinkedList()

# 새 리스트 생성(10 -> 20 -> 30)
sll.head = Node(10)
sll.head.next = Node(20)
sll.head.next.next = Node(30)

print("원래 리스트:")
sll.print_list()  # 10 -> 20 -> 30
print("-" * 30)

# 20이 들어있는 노드 조회
pos = sll.search(20)
print(f"데이터 20의 위치: {pos}번 인덱스")
print("-" * 30)

 

 

 

앞서 배운 배열과 연결 리스트의 차이점은 무엇일까

배열	연결리스트
정적 자료구조	동적 자료구조
데이터 추가 삭제 작업의 어려움	데이터 추가 삭제 작업에 용이
연속된 메모리 주소를 할당 받음 => 데이터 탐색 및 조회에 용이	연속된 메모리 주소를 할당받지 않음 => 데이터 탐색, 조회에 많은 시간 소요
구현이 간단함	배열에 비해 구현 복잡

 

 

연결리스트 장단점

장점	단점
빠른 삽입과 삭제	임의 접근이 어려움 + 역방향 탐색의 어려움
동적 자료구조	메모리 오버헤드
효율적인 메모리 사용	복잡한 구현

 

 

연결리스트는 데이터 삽입 및 삭제가 빈번한 곳, 크기를 미리 알 수 없는 동적 데이터 처리에 주로 활용된다.

• 음악 및 영상 재생목록 플레이리스트 : 이전 곡과 다음 곡이 체인처럼 연결되어 있는 양방향 연결리스트 사용
• 게임 인벤토리 : 아이템 획득 및 삭제가 빈번하게 일어나는 게임 로직에서 사용