Array, Linked List

Array(배열)은 컴퓨터 과학에서 기본적인 자료 구조 중 하나로, 동일한 자료형의 요소들을 순서대로 나열한 것이다. 배열은 연속적인 메모리 위치에 데이터 요소들을 저장하여, 인덱스를 통해 각 요소에 빠르게 접근할 수 있는 장점을 가진다.

 

대부분의 프로그래밍 언어에서 배열을 생성할 때 그 크기가 고정되며, 나중에 크기를 변경할 수 없다. 모든 배열 요소는 같은 자료형이어야 한다. 이로 인해 메모리 관리가 용이하고, 요소 접근 시간이 단축된다. 배열의 요소는 0부터 시작하는 인덱스를 사용하여 접근할 수 있다. 인덱스를 통한 접근은 O(1)의 시간 복잡도를 가진다.

 

인덱스를 사용하여 배열의 어떤 위치에도 즉시 접근할 수 있고 연속적인 메모리 할당 덕분에 메모리 사용이 효율적이다.

 

배열을 생성할 때 크기를 정해야 하며, 크기를 동적으로 변경하는 것이 어렵다. 그리고  배열 중간에 요소를 삽입하거나 삭제할 경우, 나머지 요소들을 이동해야 하므로 비효율적이다.

 

간단한 리스트 데이터를 다룰 때 유용하며, 크기가 고정되어 있고, 자주 변경되지 않는 데이터 집합에 적합하다. 수학적 계산이나 고정된 데이터 집합을 다루는 알고리즘에서 주로 사용된다.

# 배열(리스트) 생성
numbers = [1, 2, 3, 4, 5]

# 배열 요소에 접근
print(numbers[0])  # 첫 번째 요소 출력, 결과: 1

# 배열 요소 수정
numbers[2] = 10  # 세 번째 요소를 10으로 변경
print(numbers)  # 결과: [1, 2, 10, 4, 5]

# 배열에 요소 추가
numbers.append(6)  # 배열의 끝에 6 추가
print(numbers)  # 결과: [1, 2, 10, 4, 5, 6]

# 배열의 특정 위치에 요소 추가
numbers.insert(1, 20)  # 두 번째 위치에 20 추가
print(numbers)  # 결과: [1, 20, 2, 10, 4, 5, 6]

# 배열의 요소 삭제
del numbers[1]  # 두 번째 요소 삭제
print(numbers)  # 결과: [1, 2, 10, 4, 5, 6]

# 배열의 길이 확인
print(len(numbers))  # 결과: 6

# 배열을 순회하며 요소 출력
for number in numbers:
    print(number)

 

Linked List(연결 리스트)는 선형 자료 구조의 일종으로, 데이터 요소들이 노드 형태로 저장되며 각 노드는 다음 노드를 가리키는 포인터(또는 참조)를 포함한다. 연결 리스트는 배열과 비교했을 때, 동적으로 메모리를 할당하며 요소의 추가와 삭제가 유연하게 이루어진다는 특징을 가진다.

 

노드(Node)는 데이터와 다음 노드를 가리키는 포인터로 구성된다. 마지막 노드는 다음 노드가 없음을 나타내기 위해 보통 null을 포인터 값으로 갖는다.

 

헤드(Head)는 리스트의 첫 번째 노드를 가리키는 포인터이다. 리스트의 시작점 역할을 한다.

 

단일 연결 리스트(Singly Linked List)는 각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결 리스트다.

 

이중 연결 리스트(Doubly Linked List)는 각 노드가 이전 노드와 다음 노드 양쪽을 가리킨다. 양방향 탐색이 가능하다.

 

원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키는 형태로, 리스트의 끝과 시작이 연결된다.

 

배열과 달리 미리 크기를 지정할 필요가 없으며, 요소의 추가와 삭제 시 리스트의 크기가 동적으로 조절되고  필요할 때마다 메모리 공간을 할당받아 사용하기 때문에, 사용하지 않는 메모리 공간이 생기지 않는다. 포인터만 변경하면 되기 때문에, 배열에 비해 훨씬 효율적으로 데이터의 삽입과 삭제가 이루어진다.

 

배열처럼 인덱스를 통한 직접 접근이 불가능하며, 특정 요소에 접근하기 위해서는 헤드부터 순차적으로 탐색해야 한다. 그리고 각 노드가 데이터 외에도 포인터를 저장해야 하므로, 추가적인 메모리 공간이 필요하다.

 

연결 리스트는 데이터의 삽입과 삭제가 빈번하게 발생하거나, 데이터의 크기를 미리 예측하기 어려운 경우에 유용하게 사용된다. 예를 들어, 운영체제에서 프로세스 관리, 메모리 관리 등에 연결 리스트가 활용된다.

 

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 self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        #리스트의 모든 요소를 출력한다.
        cur_node = self.head
        while cur_node:
            print(cur_node.data, end=" -> ")
            cur_node = cur_node.next
        print("None")

# 연결 리스트 사용 예시
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)

llist.print_list()
# 출력: 1 -> 2 -> 3 -> None

 

C로 Linked List 구현 코드

Data-Structure-C-Language-Exercises/yunsejin at master · yunsejin/Data-Structure-C-Language-Exercises