신입생세미나 | 연결리스트를 이용한 양방향 큐(Deque)

데큐 구현한 코드 다시 설명(22.01.20)

 - 서치 연산

 - 딜리트 연산

 - 인서트 연산

양방향 큐는 데큐를 의미함, 오해를 살 수 있으니 Deque 로 고쳐줄 것

그림으로 설명할 때에는 앞뒤 노드의 주소를 저장하는 포인터를 양옆 2개로 표현하고,

pt에는 데이터와 포인터로만 나누어진 그림을 사용

같은 것을 뜻하는 것인지 질문이 들어옴 -> 다음에는 이해를 돕기 위해서는 통일된 자료를 사용하도록 유의

 

데이터가 저장할 때에는 메모리에 저장이 될 테지만 가시화된 자료처럼의 모양은 아닐 수도 길수도

첫번째 단점을 단일리스트의 단점이라고 자가판단 -> 미스

특정 위치의 데이터를 검색해내는 데에 시간소요가 큰 것은 이중리스트와 비교해서가 아니라! 배열이나 트리 구조와 비교해서임.

왜?

 

-> 시간복잡도 개념이 나왔었음. 물어볼 생각은 않고 자료에서 빼버림? 일 잘하는 인턴, 동기, 선배, 박사님께 다 여쭤보면서 시간복잡도 개념에 대해 물어봤어야 함

 

환용씨의 질문 : 첫번째 데이터 pop할 때 이중연결리스트가 왜 더 빠른가?

단일리스트와 연결리스트의 첫번째 데이터 값을 pop 할 때 속도는 비슷하다. 다만, 이중연결리스트이니 연산을 더 하면 미묘한 차이는 있을 수도 있음. 

다만 배열로 저장되었을 경우는 속도가 느려진다. 배열의 경우 pop 하면 단일/이중 연결리스트와 달라 저장공간이 정해져 있어 뒤의 값을 pop해서 없어진 곳에 채워져야 한다. 

 

-> 시간복잡도 개념

단일 연결 리스트 O(1)

이중 연결 리스트 O(1)

리스트의 경우 O(N)

 

-> 질문은 아니었지만 공부하려다 만 내용이었다.. 큰 그림 먼저 살폈어야 한 게 맞음

+-> peek : 데이터를 확인하려고 할 때, 기본적인 것이었다고 하는데.. 공부할 때 스택이 나왔으면 볼 필요 있었다.

 

배열이나 트리 구조와 달리, 특정 위치의 데이터를 검색해내는 데에 시간 소요가 큼

트리 구조(비트리)의 경우, 정렬의 특징: 왼쪽의 경우 작은 값들부터 오른쪽으로 갈수록 큰 값이 저장

어떠한 값이 들어왔을 때 대략적은 위치를 알 수 있지만, 연결리스트의 경우 하나하나 탐색해봐야 한다. 

 

추가로) 배열의 특징

size의 제한 : 100개의 공간에 10개 들어갈 경우 메모리 그대로 낭비

 

 

이중리스트의 메모리 소요가 큰 이유는?

이중리스트의 노드의 경우 prev-data-next 포인터로 다음이나 전의 데이터의 주소를 저장하게 됨. 그러니 메모리(저장공간)의 공간을 많이 차지하게 되고 소요가 크게 됨

-> 예상질문이었는데도 까먹었던 게 말이 안됨. 질문리스트 만들어서 나의 의문점이나 예상리스트에 답변 준비할 것

 

 

 

추가로 공부할 내용

*1. 배열과는 달리? 연결리스트 데이터 검색 소요가 크다?

     배열의 경우, 인덱스 가지고 있어 인덱스를 찾아감. O(1)

     연결리스트의 경우, 하나하나의 데이터를 다 거쳐가야 함. O(n)

*2. 자료구조: 순차 자료구조, 연결 자료구조 차이

3. 중간지점에서도 자료의 추가 삭제 O(1) 시간에 가능? 누구는 탐색해야 해서 O(n)시간만 가능하다고 하는데..?

4. 배열: 논리적 장소와 물리적 저장 순서가 일치하는 자료구조?

   연결 리스트: 논리적 저장순서와 물리적 저장순서가 일치하는 자료구조 라는 것은 뭘 뜻하는 것인지

5. 이중 연결 리스트를 이용한 데크에서 데이터 delete, insert, search 코드 구현하고 말로 발표(22.01.20)