기술 면접 - 자료 구조 (선형 구조)

자료구조란?

• 데이터의 표현 및 저장 방법

선형 자료구조

• 데이터를 선의 형태로, 나란히 혹은 일렬로 저장하는 방식

1 . 순차 리스트

---

• 배열을 기반으로 만든 리스트
• 논리적 저장 순서와 물리적 저장 순서가 일치함
• 찾고자 하는 원소의 인덱스 값만 알고 있다면 O(1)에 해당 원소로 접근할 수 있음

• add
  • 배열의 끝에 원소를 추가, 위치를 알고 있기 때문에, O(1)
• remove
  • 배열의 원소를 지웠을 때, 그 뒤의 원소들을 앞으로 한 칸씩 밀어줘야 함, O(N)
• get
  • 인덱스를 알고 있다면, 시작 위치 + 인덱스로 주소를 알 수 있음, O(1)
• Contains
  • 어떤 원소를 가지고 있는지 확인, 모든 원소를 순서대로 찾아봐야 한다, O(N)

2. 연결 리스트

---

• 메모리의 동적 할당을 기반으로 구현된 리스트
• 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있음

• add

  • 리스트의 끝에 노드 하나를 추가, O(1)

• remove

  • 지우고자 하는 노드를 지우고, 앞 뒤 노드들을 연결시켜주면 됨
  • 순차 리스트처럼 쉬프트 동작이 필요하지 않다!, O(1)

• get

  • 첫 노드부터, 순서대로 확인해야 한다, O(N)

• Contains

  • 마찬가지로, 순서대로 탐색, O(N)

• 연결 리스트가 insert와 remove를 O(1)에 할 수 있다는 장점이 있다고는 하지만 엄밀히 말하면, 삽입, 삭제하고자 하는 위치까지 가는 행위가 O(N)이 걸리기 때문에 빠르다고는 할 수 없다

3. 스택

---

• 선형 자료구조의 일종으로 Last In First Out을 제공하는 자료구조이다
• 나중에 들어간 원소가 먼저 나옴

• PUSH
  • 원소를 넣는다, 마지막 위치에 넣으면 되기 때문에, O(1)
• POP
  • 가장 위 원소를 뺀다, O(1)
• PEEK
  • 마지막 위치에 해당하는 원소를 읽는다, O(1)

• 배열 기반, 연결리스트 기반 둘 다 가능하지만 서로 장단점이 존재함

4. 큐

---

• 선형 자료구조의 일종으로 First In First Out을 제공하는 자료구조이다
• 선입 선출 구조
• 대기줄을 표현할 때 자주 사용함

• 배열을 사용해서 구현한다면, 앞 뒤를 연결시키는 환형 버퍼를 사용해서 구현