프로그래밍 면접 이렇게 준비한다 (8) [책리뷰 & Book review]

 

프로그래밍 면접 이렇게 준비한다 (8)

[책리뷰 & Book review]

 

 

[책리뷰 & Book review]

 

 

 

 

단일 연결 리스트
이중 연결 리스트
원형 연결 리스트
이렇게 3가지 연결리스트의 종류와 (원소와 꼬리원소)가 있다.

 

단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트

연결 리스트는 데이터의 선형 집합으로, 데이터의 순서가 메모리에 물리적으로 연결된 구조에 의해 결정되는 데이터 구조입니다. 이는 다음과 같이 세 가지 주요 유형으로 나뉩니다.

단일 연결 리스트: 각 노드가 데이터와 다음 노드에 대한 링크로 구성되어 있습니다. 마지막 노드는 null 값을 가집니다.
이중 연결 리스트: 각 노드가 데이터와 두 개의 링크로 구성되어 있습니다. 하나는 이전 노드를, 다른 하나는 다음 노드를 가리킵니다. 시작과 끝 노드는 null을 가리킵니다.
원형 연결 리스트: 단일 또는 이중 연결 리스트와 유사하지만, 마지막 노드가 첫 번째 노드, 즉 헤드를 가리킵니다. 

이로 인해 리스트 전체를 계속 순회할 수 있습니다.

* **단일 연결 리스트**
    * 각 원소는 데이터와 다음 원소를 가리키는 포인터를 가지고 있다.
    * 데이터에 대한 순차적 접근만 가능하다.
    * 삽입과 삭제가 상대적으로 쉽다.

* **이중 연결 리스트**

    * 각 원소는 데이터와 다음 원소를 가리키는 포인터와 이전 원소를 가리키는 포인터를 가지고 있다.
    * 데이터에 대한 순차적 접근과 역순 접근이 모두 가능하다.
    * 삽입과 삭제가 상대적으로 어렵다.

* **원형 연결 리스트**

    * 마지막 원소가 첫 번째 원소를 가리키는 단일 연결 리스트이다.
    * 데이터에 대한 순환적 접근이 가능하다.
    * 삽입과 삭제가 상대적으로 쉽다.

 

스택 구현법

1. 기본적인 자료구조에 대한 지식
2. 자료구조를 조작하기 위한 루틴을 만드는 능력
3. 일련이 루틴에 대한 일관성 있는 인터페이스를 설계하는 능력

스택은 LIFO(Last In First Out) 원칙에 따라 작동하는 추상적인 자료형입니다. 스택을 구현하는 것은 다음과 같은 3가지 주요 능력을 필요로 합니다.

기본적인 자료구조에 대한 지식: 스택은 배열이나 연결 리스트 등의 기본적인 자료구조를 사용하여 구현할 수 있습니다.
자료구조를 조작하기 위한 루틴을 만드는 능력: 스택은 주로 'push'와 'pop' 두 가지 기본적인 연산을 사용합니다. 이들 연산을 효과적으로 구현하는 것이 중요합니다.
일련의 루틴에 대한 일관성 있는 인터페이스를 설계하는 능력: 사용자가 스택을 쉽게 사용할 수 있도록 인터페이스를 설계하는 것이 필요합니다.

스택은 선입선출(First-In-Last-Out) 방식으로 데이터를 저장하는 자료 구조이다. 

스택은 다음과 같은 방법으로 구현할 수 있다.

* 배열을 사용하여 구현하기
* 연결 리스트를 사용하여 구현하기

 

백엔드 개발자는 기본적인 자료 구조에 대한 지식이 있어야 한다. 기본적인 자료 구조에는 다음과 같은 것들이 있다.

* 배열
* 연결 리스트
* 스택
* 큐
* 해시 테이블
* 트리
* 그래프

 

 

 

 

 

head 포인터는 무엇이며 꼬리원소는 무엇인가?

head 포인터와 꼬리원소란?

연결 리스트에서 'head'는 보통 리스트의 첫 번째 노드를 가리키는 포인터를 의미합니다. 

이 포인터를 통해 리스트의 모든 노드에 접근할 수 있습니다. 반면 '꼬리원소'는 보통 리스트의 마지막 노드를 의미합니다.

 

* **head 포인터**
   * 연결 리스트의 첫 번째 원소를 가리키는 포인터이다.
    * 연결 리스트를 순회할 때 시작점 역할을 한다.

 

 

 

 

 

 

너비 우선 검색과 리스트 단층화는 어떤 관계가있는가?

너비 우선 검색과 리스트 단층화의 관계

너비 우선 검색(BFS, Breadth-First Search)은 트리나 그래프 등의 자료구조를 탐색하는 알고리즘 중 하나로, 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방식을 사용합니다. 이는 리스트 단층화와 관련이 있는데, 특히 트리를 단일 리스트로 변환하거나 '플래튼'하는 과정에서 BFS가 흔히 사용됩니다.

너비 우선 검색은 그래프를 검색하는 알고리즘 중 하나이다. 너비 우선 검색은 리스트 단층화를 사용하여 구현할 수 있다.

 

 

 

 

순환형 리스트와 비순환형 리스트 는 무엇인가?

순환형 리스트와 비순환형 리스트란?

순환형 리스트는 마지막 노드가 리스트 내의 특정 노드를 가리키는 형태의 연결 리스트를 의미합니다. 이로 인해 노드를 계속 순회하는 무한 루프가 발생할 수 있습니다. 반면 비순환형 리스트는 마지막 노드가 null을 가리키므로, 리스트의 끝에 도달하면 순회가 종료됩니다.

* **순환형 리스트**

    * 마지막 원소가 첫 번째 원소를 가리키는 연결 리스트이다.

* **비순환형 리스트**

    * 마지막 원소가 null을 가리키는 연결 리스트이다.

 

 

 

 

 

 

 

 

 

종주는 무엇인가?

 

종주란?

종주는 리스트나 배열 등의 자료구조를 처음부터 끝까지 순회하는 것을 의미합니다. 이는 데이터의 모든 요소를 검사하거나 조작해야 할 때 흔히 수행됩니다. 연결 리스트의 경우, 헤드에서 시작하여 각 노드의 'next' 링크를 따라 이동하면서 종주를 수행할 수 있습니다.

 

   * **선순회**

        * 데이터가 첫 번째 원소에서 마지막 원소까지 순차적으로 이동하는 방향이다.

    * **역순회**

        * 데이터가 마지막 원소에서 첫 번째 원소까지 역순으로 이동하는 방향이다.