LinkedList와 ArrayList의 차이점이 대체 뭐야?

LinkedList와 LinkedArray의 차이점

1. LinkedList (연결 리스트)

• 구조: 각 요소(노드)가 다음 노드를 가리키는 포인터를 포함합니다.
• 접근 방식: 순차적 접근. 특정 인덱스에 접근하려면 처음부터 노드를 따라가야 합니다.
• 삽입/삭제: 특정 위치에 요소를 추가하거나 삭제하는 것이 빠릅니다. 이전 노드의 포인터만 변경하면 됩니다.
• 메모리 사용: 각 노드는 데이터와 함께 다음 노드를 가리키는 추가적인 포인터 공간을 필요로 합니다.

2. LinkedArray (연결 배열, 더 일반적으로는 ArrayList라고 불림)

• 구조: 배열 기반의 구조에서, 요소들이 메모리 상에서 연속적으로 위치합니다.
• 접근 방식: 인덱스 기반 접근. 특정 인덱스의 요소에 빠르게 접근할 수 있습니다.
• 삽입/삭제: 중간에 요소를 삽입하거나 삭제하는 경우, 배열을 재조정해야 하므로 비효율적일 수 있습니다.
• 메모리 사용: 고정된 크기를 가지며, 크기 조정을 위해 전체 배열을 재할당해야 할 수 있습니다.

예시 코드

LinkedList 예시 (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 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 display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 사용 예시
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.display()  # 1 -> 2 -> 3 -> None 출력

ArrayList (Python에서는 List) 예시

class ArrayList:
    def __init__(self):
        self.array = []

    def append(self, data):
        self.array.append(data)

    def delete(self, index):
        if index < len(self.array):
            del self.array[index]

    def display(self):
        print(self.array)

# 사용 예시
alist = ArrayList()
alist.append(1)
alist.append(2)
alist.append(3)
alist.display()  # [1, 2, 3] 출력
alist.delete(1)
alist.display()  # [1, 3] 출력

Python의 list는 내부적으로 동적 배열을 사용하여 구현된 ArrayList와 유사합니다.

연결 리스트와 달리, 리스트는 인덱스를 통해 빠르게 요소에 접근할 수 있지만, 삽입과 삭제에서는 더 많은 작업이 필요할 수 있습니다.