[다시 알고리즘] 자료구조 마스터 (리스트)

ArrayList와 LinkedList

한눈에 비교하기

• 두 자료구조의 가장 큰 차이는 데이터를 메모리에 어떻게 저장하느냐에 있다
• ArrayList
  • 연속된 메모리 공간에 저장
  • 조회 : 매우 빠름 ($O(1)$)
  • 삽입 삭제 : 느림 (데이터를 밀거나 당겨야 함)
  • 메모리 : 미리 할당된 크기 사용
• LinkedList
  • 노드(Node)가 데이터와 다음 주소를 가짐
  • 조회 : 느림 (앞에서부터 찾아야 함, $O(n)$)
  • 삽입 삭제 : 빠름 (연결 선만 바꾸면 됨)
  • 메모리 : 필요할 때마다 동적으로 추가

# 1. ArrayList (Python List)
array_list = [10, 20, 30]
array_list.append(40) # 추가
print(array_list[1])  # 조회: 20

# 2. LinkedList (간단한 구현)
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

node1 = Node(10)
node2 = Node(20)
node1.next = node2 # 10 다음에 20을 연결

// 1. ArrayList (JS Array)
const arrayList = [10, 20, 30];
arrayList.push(40);        // 추가
console.log(arrayList[1]); // 조회: 20

// 2. LinkedList (간단한 구현)
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

const head = new Node(10);
head.next = new Node(20); // 참조를 통해 연결

어떤 자료구조를 써야 하는 가?

• ArrayList
  • 데이터의 개수가 크게 변하지 않을 때
  • 특정 위치의 데이터를 자주 읽어야 할 때 (인덱스 접근)
• LinkedList
  • 데이터의 삽입과 삭제가 빈번하게 일어날 때
  • 데이터의 총 개수를 가늠하기 어려울 때