SKYLIGHT STUDIO

일단 여기서 '리스트'는 전형적인 '선형 리스트'를 의미한다고 보면 된다. 우선 면접에서 이런 질문을 던진다면... 난 이 답변부터 이야기하겠다. 선형 리스트는 ‘순차적으로’ 구현한 것이기에(연속된 메모리) 결과론적으로 Random Access(임의 접근)이 가능해지게 되므로 상대적으로 접근과 탐색에 강점을 가지게 된다. 연결 리스트는 연속된 메모리 공간에 저장할 필요가 없는 특성상 임의 접근이 불가능하며, 그 대신 저장 공간의 활용이 상당히 자유로워지게 되는 것이다. 이제 둘을 시간복잡도 관련 관점으로 한번 비교해보자. 연결 리스트 예제 using System; class Node { public T Data; public Node Next; public Node(T data) { Data = data..

ADT(추상적 자료형) : 집합, 리스트, 큐, 트리 등의 자료 자체의 형태와 그 자료에 관계된 연산들을 수학적으로만 정의한 것. 그리고 자료구조는 추상적 자료형이 정의한 연산들을 구현한 구현체를 가리키는 말이다 음... 당연히 이렇게 말하면 이해가 불가능하니, 예를 들어보자. 스택 ADT는 데이터를 삽입하는 push(), 데이터를 제거하는 pop(), 스택의 상단 요소를 확인하는 peek 등의 연산을 정의한다. 스택을 구현할 때, 배열이나 연결 리스트와 같은 자료구조를 사용하여 구체적인 스택(Call Stack)을 구현할 수 있는 것이다. 중요한 것은, 스택 ADT 그 자체는 이런 구체적인 구현에 관련된 세부 정보까지는 제공하지 않는다는 것. 대강 이미지로 예를 들자면 다음과 같다. 이 이미지도 정확할..