[Interview] List(Array, Linked List)

리스트

리스트(List)란?

데이터를 순서대로 저장하며 중복된 데이터의 저장이 가능한 선형 자료 구조

• Ex) 배열(Array), 연결 리스트(Linked List)

Array

순차적으로 데이터를 저장

• 배열의 각 요소는 메모리에서 연속적으로 위치
• 원소의 물리적 저장 순서 = 원소의 논리적 순서

장점

• 0부터 시작하는 index를 통해 특정 요소를 찾고 조작이 가능(랜덤 엑세스가 빠름)
• 메모리 사용이 효율적(연속된 메모리 공간을 사용함)

단점

• 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들을 한 칸씩 뒤로 밀거나 당겨줘야 하는 단점 존재
• 이러한 이유로 Array는 정보가 자주 삭제되거나 추가되는 데이터를 담기에 적절하지 않음

Array를 적용해서 데이터를 구현하면 좋은 예

• 학생 성적관리
  • 성적의 경우 데이터가 빈번하게 변경되지 않고, 빠른 조회가 중요하기 때문에 배열이 적합
  • 만약 데이터가 빈번하게 변경되고, 순서의 보장이 중요하지 않다면 다른 자료구조 선택이 나을 수 있음

시간 복잡도

O(1)

• index를 통한 조회

O(n)

• 특정 값을 조회: 모든 요소를 처음부터 끝까지 차례대로 확인
• 삽입, 삭제: 이후 요소를 이동시켜야 하기 때문
  • 인덱스를 통해 탐색 후 삽입, 삭제의 시간복잡도 자체는 O(1)

Linked List

메모리의 동적할당을 기반으로 구현된 리스트

• 원소의 물리적 저장 순서 ≠ 원소의 논리적 순서

장점

• 메모리를 동적으로 할당하여 유연하게 크기를 조절
• 데이터의 중간에 삽입, 삭제를 하더라도 전체를 순회하지 않아도 이전 값과 다음값이 가리켰던 주소값만 수정하여 연결시켜주면 되기 때문에 삽입과 삭제가 빈번한 가변적인 리스트를 구현할 때 사용
  • 삽입, 삭제가 느린 배열의 단점을 극복

단점

• 배열과 달리 연속적인 메모리 주소를 할당 받지 않기 때문에 임의 접근이 불가능
  • Array에선 index를 가지고 빠른 검색을 수행하지만, Linked LIst는 헤드에서 부터 순회하므로 느린 탐색 시간을 가짐
  • 연결 리스트에서는 탐색을 위해 순차 접근(Sequential Access)
• 메모리 사용이 배열에 비해 상대적으로 많다.

1. 단순 연결 리스트(Singly Linked List)

노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조

헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킴

Null을 가리키는 노드가 해당 리스트의 마지막임을 보증

장점

• 삽입과 삭제가 헤드에서 빠르게 수행됨

단점

• 역방향 탐색이 불가능

시간 복잡도

O(1)

• 처음이나 끝의 삽입, 삭제

O(n)

• 탐색
• 특정 위치의 삽입, 삭제

2. 이중 연결 리스트(Doubly Linked LIst)

두개의 링크 필드(prev, next)와 한개의 노드(data)로 구성

양쪽 방향으로 순회할 수 있도록 노드를 연결

장점

• 양방향 탐색이 가능

단점

• 단순 연결 리스트보다 각 노드의 포인터가 추가되어 메모리 사용량이 많아짐

시간 복잡도

O(1)

• 처음이나 끝의 삽입, 삭제

O(n)

• 탐색
• 특정 위치의 삽입, 삭제

Reference
https://juyeop.tistory.com/51 https://dev-coco.tistory.com/159 https://velog.io/@humblechoi/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-List https://velog.io/@yyj8771/%EB%A6%AC%EC%8A%A4%ED%8A%B8-List-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0