[자료구조] 3일차 자료구조란? 주문 관리 시스템 문제 해결하기

주문 관리 시스템

: 주문 생성, 주문 제거, 주문 조회의 기능을 가진 주문 관리 시스템을 구현해야한다.

• 연결리스트로 구현했을 때 처리 속도가 너무 느림. (따라가면서 찾은 후 삭제 : 비효율)
• 연결리스트의 특정 노드를 삭제하기 위해서 그 특정 노드에 접근하는 과정이 필요.
• 연결리스트의 특성에 의해 특정 원소에 접근하기 위해서는 시작 원소부터 하나씩 따라가야함.
  • 어떤 노드를 삭제하기 위해선 이전 노드와 다음 노드를 알고있어야함.
  • 이 단점 개선 위해 연결 리스트 내에 딕셔너리를 두고, 모든 노드들의 정보를 저장하고 있도록 함.
  • 딕셔너리: 내부적으로 해시 테이블이라는 자료구조로 동작 어떤 key에 대한 value를 o(1)의 시간 복잡도로 접근

 

: 주문번호에 대해 각 노드를 대응시키는 딕셔너리를 하나 만들어두면 removeOrder 함수를 수행할 때 삭제할 노드를 o(1)만에 찾아낼 수 있다.

 

 

이중 연결 리스트

: 노드에 포인터가 두 개가 있고 각각 이전 노드와 다음 노드를 가리키는 형태의 연결리스트

예) 노드3 제거시

→ 노드3에 바로 접근을 하고 이전 노드 다음 노드 접근을 해서 노드2에서 바로 4로 연결

배열이든 연결리스트든 주문 번호가 주어졌을 때 해당 주문이 몇 번째인지 알기 위해서는 맨 첫 번째 주문부터 하나씩 확인해봐야한다.

 

 

배열이 더 빠른 이유?

: 배열의 요소들은 컴퓨터에서 물리적으로 가깝기 때문

연결리스트는 각각 별도의 객체들을 임의로 연결하는 방식으로 구현되지만 배열의 경우, 각 요소들이 컴퓨터 내부에서 매우 가깝게 위치

 

좌) 배열, 우) 연결리스트

배열 : 메모리상에서 인접하고 있으니까 인덱스간의 이동이 빠름.

연결리스트: 별도의 객체들이 있고 포인터라는 형태로 임의로 엮은 것.

---

따라서 전체 요소를 순회하는 연산 또한 배열이 더 유리

데이터의 입출력과 문제 상황을 잘 파악하여 적절한 자료구조 선택하기