선형 리스트 (Linear List)와 연결 리스트 (Linked List) 차이

선형 리스트(Linear List)와 연결 리스트(Linked List)는 데이터를 저장하는 두 가지 기본적인 자료구조입니다. 각각의 특징과 코드 예시를 설명해보겠습니다.

 

선형 리스트 (Linear List)

선형 리스트는 배열(Array)로 구현되며, 연속된 메모리 공간에 데이터가 저장됩니다. 데이터의 삽입, 삭제에 대한 연산이 비효율적일 수 있습니다.

아래는 Python 코드로 표현된 선형 리스트의 예시입니다:

 

 

# 선형 리스트 생성 및 초기화
linear_list = [10, 20, 30, 40, 50]

# 데이터 삽입
linear_list.append(60)

# 데이터 조회
print(linear_list[2])  # 출력: 30

# 데이터 삭제
linear_list.remove(40)

# 전체 리스트 출력
print(linear_list)  # 출력: [10, 20, 30, 50, 60]

 

 

 

연결 리스트 (Linked List)

연결 리스트는 노드(Node)들로 구성되며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(링크)로 이루어져 있습니다. 연속된 메모리 공간을 필요로 하지 않아 데이터의 삽입, 삭제에 효율적입니다.

연결 리스트는 크게 단일 연결 리스트(Singly Linked List)와 이중 연결 리스트(Doubly Linked List)로 나뉩니다. 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 모두 가리키는 구조입니다.

아래는 Python 코드로 표현된 단일 연결 리스트의 예시입니다:

 

 

# 연결 리스트의 노드 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 연결 리스트 생성 및 초기화
class LinkedList:
    def __init__(self):
        self.head = None

    # 데이터 삽입
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    # 데이터 삭제
    def remove(self, target_data):
        if not self.head:
            return
        if self.head.data == target_data:
            self.head = self.head.next
            return
        current = self.head
        while current.next:
            if current.next.data == target_data:
                current.next = current.next.next
                return
            current = current.next

    # 전체 리스트 출력
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 연결 리스트 생성 및 조작
linked_list = LinkedList()
linked_list.append(10)
linked_list.append(20)
linked_list.append(30)
linked_list.display()  # 출력: 10 -> 20 -> 30 -> None

linked_list.remove(20)
linked_list.display()  # 출력: 10 -> 30 -> None

 

 

 

위 코드에서 Node 클래스는 연결 리스트의 각 노드를 나타내며, LinkedList 클래스는 노드들을 관리하는 연결 리스트를 나타냅니다. 노드 추가, 삭제, 리스트 출력 등의 연산이 가능합니다.