BJ.22 리스트(list)를 설명합니다. array list와 linked list의 개념과 차이를 한방에 정리합니다! - ko

네, 반갑습니다. 오늘이 영상을 끝까지 보신 후엔 ADT의 관점에서

리스트의 개념과 그리고이 리스트의 구현체인 어레이 리스트, 링크드

리스트를 이해하게 됩니다. 자, 그럼 오늘도 곡싱. 자, 그럼 먼저

ADT의 관점에서 리스트를 한번 살펴볼게요.이 리스트라는 것은 값들을

저장하는 추상 자료 형입니다.이 리스트는 특징이 있는데요. 일단

순서가 있고요. 그리고 중복을 허용을 합니다. 자, 그래서이 리스트는 언제

쓸 수 있나 이런 경우에 쓸 수 있겠죠. 객관식 문제의 정답을

저장해야 될 때 이럴 때 리스트를 쓸 수 있을 겁니다. 지금이 오른쪽에

보시면이 100가지 문제가 있거든요. 사지 선다형으로 100 가지 문제가

있는데이 100개의 문제에 대해서 다 정답들이 있을 거잖아요. 그럼이

정답들을 리스트에 관리할 수 있는 거죠. 그러면이 정답에는 순서가

중요하니깐 순서대로 차근차근 각 정답들을 저장을 할 거고요. 또 각

정답이 지금 보면 사지 선다형이기 때문에 각 정답들이 이제 중복이 될

수가 있겠죠. 그래서 이런 경우에 리스트에 딱 저장을 하면 좋을 것

같다는 생각이 들고요. 그러면 리스트는 또 언제 쓸 수 있을까요?

이런 경우에도 쓸 수 있겠죠. 일반적으로 사용되는 프로그래밍 언어

순위를 저장하고 싶을 때도 리스트를 사용할 수 있을 겁니다. 지금이

오른쪽에 보시는 자료는 2021년 스택 오버플로우에서 개발자들에게 설문

조사한 결과인데요. 지금 보시면 자바스크립트가 제일 자주 사용되는

언어로 뽑혔고 세 번째 파이썬, 다섯 번째 자바 뭐 이런 식으로 다 랭킹이

있잖아요. 그러면이 랭킹을 순서대로 저장하는게 좋으니까 이런 경우에도

리스트를 사용할 수 있겠죠. 물론 지금이 경우에는 값들이 중복될 일은

없을 거예요. 바로 앞에 봤던 얘랑은 다르게 값들 자체가 중복될 일은

없겠지만 랭킹을 순서대로 저장을 해야 되기 때문에 이런 경우에는 리스트가

또 적절한 거죠. 자, 이것 말고도 리스트는 언제 쓸 수 있을까요? 추후

영상에도 다루게 되겠지만이 셋이나 맵을 사용하는게 더 적절한 상황이

아니라면 일반적으로 거의 대부분은 리스트를 사용한다고 봐도 무리가 없을

것 같아요. 가령 D TV에서 데이터를 읽고 왔을 때 만약에 여러

개의 데이터를 읽고 온다면 그 여러 개의 데이터를 어디에 담아야

되잖아요. 그러면 만만한게 리스트기 때문에 이런 경우에도 리스트를

사용하게 되거든요. 이런 식으로 셋시나 맵을 사용하는게 더 적절한

상황이 아니라면 리스트를 쓰면 된다. 그렇게 이해를 하시면 될 거 같아요.

자, 그러면 이제 본격적으로이 리스트의 구현체를 살펴볼게요. 앞에

설명은 ADT 관점에서 살펴본 거라면 이제는이 리스트를 실제로 구현하는

방법들을 살펴보는 거죠.이 이 리스트 구현체에는 대표적으로 두 가지가

있는데요. 하나는 레이 리스트가 있고 하나는 링크드 리스트가 있습니다.

먼저 리스트부터 살펴보면이 어레이 리스트는 베어를 사용해서 리스트를

구현하는 방식입니다. 그래서 예를 들어서 이마만한 크기의 배열을 하나

잡아 놓고 그 안에다가 이런 식으로 데이터를 차곡차곡 저장을 하는 거죠.

그러면이 어레이 리스트가 어떻게 동작하는지 본격적으로 여러 가지

동작들과 함께 살펴보도록 할게요. 여기에 있는이 동작들은 그냥 제가

임의로 이름을 붙인 거라서이 각 프로그래밍 언어마다 메서드나 함수

이름은 조금씩 다를 수가 있어요. 자, 어쨌든 그럼 하나하나 한번

실행을 해 보겠습니다. 먼저 어펜드 10이에요. 그러면은 지금이 배열이

크기가네 개짜리인 배열이 하나 잡혀 있는 거잖아요. 그러면 여기에 어드

10이니까 아직 아무것도 없기 때문에 맨 앞쪽에 10을 넣습니다. 그리고

어드 20을 하면 이제 끝쪽에 계속 채우는 거거든요. 그러면 그다음

자리에 20을 넣어요. 그리고 여기서 이제 인트를 하게 되는데이 인트를

보시게 되면 지금 두 가지 파라미터가 있는데 하나는 0이고 하나는

30이거든요. 그러면 값을 30이라는 값을 넣을 건데이 앞에 있는 0은

뭐냐면 0 번째 인덱스에 30을 넣을 거다라는 의미예요. 그 말은 무슨

말이냐면 지금이 위치에 30을 넣겠다는 건데 지금 이미 10이라는

값이 있기 때문에 오른쪽으로 데이터들을 다 시프트를 시켜 줘야

돼서 그럼 이제 시프트를 시켜 보겠습니다. 이렇게 하나하나 시프트를

하게 되면 이제 여기에 20이 들어가게 되고 원래 20이 있던

자리에는 이제 10이 들어가게 되죠. 그리고 이제이 원래 10이 있던

자리에 30이 들어가게 됩니다. 그래서 지금 보시는 것처럼이 어레이

리스트에 값을 넣게 되면 그 공간을 마련하기 위해서 데이터 시프트가

일어난다. 그만큼 시간이 좀 더 딜레이된다. 그렇게 이해를 하시면 될

거 같고요. 다시 그러면이어서 쭉 실행을 해 보겠습니다. 이제 어드

10이라서 이제 끝자리에 또 10을 넣는 거죠. 그리고 이제 개 2를

호출을 합니다. 이것은 뭐냐면 인덱스 2번 위치에 있는 값을 가져오라는

거거든요. 그럼 인덱스는 우리가 이전 영상에서 배웠던 것처럼 지금

배열이니까 인덱스는 0부터 시작을 하죠. 그래서 0 1이면 지금 여기

위치에 있는 값을 가지고 오라는 그런 요청이기 때문에 이제이 개를 하게

되면 얘는 20이라는 값을 반환을 하게 되는 거죠. 자, 그리고 나서

이제 다시 또 업핸드 40이 호출이 됐습니다. 그런데 지금 공간이

없잖아요. 이제 더 이상 넣을 공간이 없어요. 꽉 차 있기 때문에. 그럼

이때 이제 어떻게 동작을 하냐면 지금 현재 크기가네 개짜리인 배열보다 더

큰 배열을 하나 만들어요. 지금은 예를 들어서 그냥 여덟 개짜리를

만든다 하겠습니다. 이렇게 여덟 개짜리를 만들고요. 원래

배열에 있던 값들을 이렇게 다 카피를 합니다. 그래서 30 20 10

이렇게 카피를 하게 되고 그리고 이제이 자리에 이제 40을 넣게 되는

거죠. 이해가 되시죠? 그리고 나서 이제 얘는 뭐 이제 더 이상 사용하지

않게 되는 겁니다. 자, 이제 계속 다시이어서 실행을 해 볼게요. 이제

컨테인즈 50이 호출이 됐습니다.이 말은이 어레이 리스트에 50이라는

값이 있으면 트루를 리턴하고 없으면 폴스를 리턴하라는 의미거든요. 그러면

이때 이제 어레이 리스트에서이 0 번째부터 차근차근 하나하나씩 확인을

합니다. 0 번째부터 이렇게 쭉 확인을 해요. 근데 지금 50이라는

값이 어레이 리스트에 없기 때문에 전체 지금 아이템이 다섯 개가

있는데이 다섯 개를 다 확인해도 없었기 때문에 이때는이 컨테인즈가

폴스를 리턴하게 되겠죠. 자, 이처럼 뭔가를 찾을 때, 탐색하게 될 때는

최악의 상황에는이 어레이 리스트에 있는 모든 아이템들을 한 번씩 확인해

봐야 된다. 이런 특징이 있다는 거를 또 이해를 하시면 됩니다. 자,이어서

다음 동작을 수행해 봅시다. 이제 리무브 10을 하게 되는데 이거는

무슨 말이냐면 어레이 리스트에서 10이 있으면 그 10을 지워 주라는

얘기거든요. 그러면 여기도 일단은 10을 찾아야 돼요.이 어레이

리스트에 10이 없을 수도 있으니까 일단 10을 찾아야 되잖아요. 그러면

마찬가지로 아마 대부분의 프로그래밍 언어가 비슷할 텐데 앞에서부터

찾거든요. 그러면은 여기를 먼저 확인합니다. 그다음 여기를 확인해요.

근데 지금 10이 있잖아요. 그러면 이제이 친구를 이제 지워 줘야 되는

거죠.이 이 10이라는 친구를 지워 주게 되면 이제이 공간이

비결되잖아요. 그러면이 공간을 또 메꿔 줘야 돼요. 그래서이 공간을

메꿔 주기 위해서 다 또 이렇게 시프트가 발생을 해야 됩니다. 그래서

20을 앞으로 한 칸 당기고 마찬가지로 원래 20이 있던 자리에

10을 써 주게 되고요. 원래 10이 있던 자리에 40을 써 주게 되고요.

그리고 원래 40이 있던 자리는 이제 지워 주게 됩니다. 자, 그리고 이제

마지막 동작을 한번 해 볼게요. 지금이 마지막 동작은 rem리브

2라고 되어 있는데 이거는이 인덱스로이

2번이 2번 위치에 있는 값을 지워 주라는 얘기거든요. 그럼 얘도

똑같아요. 2번 위치에 있는 값을 일단 지워 주고 또 시프트를 해 줘야

돼요. 빈 공간을 메꿔 줘야 되니까. 그러면은이 40이라는 값을 앞으로 또

이렇게 옮겨 줘야 되겠죠. 그러면 이제이 위치에 40이 들어가고 기존에

40이 있던 위치는 또 비워 줘야 됩니다. 그래서 최종적으로 이런

모습이 되는 거죠. 자, 이런 식으로 어레이 리스트가 동작을 한다. 이해를

하시면 될 거 같습니다. 그럼 이번에는 링크드 리스트에 대해서

살펴볼게요.이 링크드 리스트는 노드를 연결시키는 형태로 구현이 돼요. 지금

밑에 보시는 이런 것들 있잖아요. 요런 것들 하나하나가 다 노드고요.이

노드에 보면 값 자체를 저장하는 공간이 있고 그다음에 다음 노드를

가르키는 포인트 혹은 그 레퍼런스를 저장하는 위치가 또 따로 있거든요.

그래서이 노드들이 서로 연결이 돼요. 이런 식으로 앞에 노드가 그다음

노드를 가르키고 또 그다음 노드는 마찬가지로 값을 저장하는 위치가 따로

있고 다음 노드를 가르키는 레퍼런스를 따로 저장하고 있어서 그 레퍼런스가

또 다음 노드를 가르키고 이런 식으로 동작을 하게 되는 겁니다. 그리고

가장 끝에 있는 노드는 가르키는게 더 이상 없기 때문에 이제 자바로 치면은

널 아무것도 가르키는게 없다라는 뜻에 그 널을 값으로 가지게 되는 거죠.

그리고이 링크드 리스트는 처음 부분을 가르치는 헤드라는게 있고이 리스트의

마지막 노드를 가르키는이 테일이라는 또 레퍼런스들이 이렇게 각각 있다고

이해를 하시면 되겠습니다. 사실이 링크드 리스트랑 어레이

리스트의 가장 큰 차이는 메모리에 어떻게 저장되느냐이 차인데요. 아까

어레이 리스트 같은 경우에는 배열을 쓰기 때문에 배열은 앞선 영상에서

살펴봤던 것처럼 연속적인 메모리 공간의 데이터를 저장하는 거라면이

링크드 리스트는 노드 각각이 각 포인트를 통해서 다음 노드를 가르키는

형태로 관리가 되기 때문에이 메모리 공간상에서 따로따로 이렇게 띄엄띄엄

저장이 된다고 이해를 하시면 될 거 같아요. 그래서 지금 보시면은이

친구가이 메모리상에서 따라가면이 넥스트라는 포인트이 레퍼런스가 결국은

다음번 노드를 가르킨다고 했죠. 그러면 그 메모리 어딘가에 있는 다음

번 노드를 가르치게 되고 그 다음 번 노드 역시도 그 넥스트라고 표시된이

레퍼런스를 통해서 메모리 어딘가에 있는 또 다음 노드를 이런 식으로

가르키게 되는 거죠. 그래서 핵심은 메모리상에서 링크드 리스트가 이런

형태로 저장이 된다. 그렇게 이해를 하시면 될 거 같아요. 자, 그러면이

링크드 리스트도 이런 여러 동작에 따라서 어떤 식으로 변화가 일어나는지

살펴보도록 할게요. 자, 기본적으로 먼저 어,이 헤드라는이 링크드

리스트의 첫 번째 노드를 가르치는이 헤드라는 걸 하나 만들어 놓고요.

보통이 헤드 하나만 두고도 구현할 수는 있습니다만 이번 얘 같은

경우에는 테일도 같이 사용하도록 하겠습니다. 그래서 테일은 링크드

리스트의 마지막 노드를 가르킨다고 했죠. 현재이 헤드와 테일이 가르키는

것은 아무도 없는 상태에서 이제이 어드 10십을 호출하면 어떤 식으로

동작을 하느냐? 일단 노드를 하나 만들죠. 노드를 하나 만들고이 노드의

10이라는 값을 넣습니다. 지금 현재이 10이 가르키는 다음 번

노드는 아무것도 없는 상태기 때문에 따로 화살표는 표시하지 않겠습니다.

그리고 이제이 헤드와 테일은 방금 만들어진이 노드를 가르쳐야 되겠죠.

자,이 상태에서 이제 어드 20을 하게 되면이 꼬리에 하나 더 붙이는

거잖아요. 그러면 일단 노드를 하나 또 새로 만듭니다. 20이라는 값을

저장하는 노드를 하나 새로 만들고 이제이 꼬리에 붙이는 거기 때문에

기존에이 테일이 가르키고 있던이 노드이 노드가 이제 방금 만들어진

20이라는 값을 가지는 노드를 가르키도록 만들어 줘야 돼요. 그리고

나서 이제이 테일이 방금 붙은이 20이라는 노드를 또 가르키도록 바꿔

줘야 되겠죠. 그러면 이제 테일은 새로 만들어진 노드를 가르키게

됩니다. 자,이 상태에서 이제 또 인트 0 30을 해 볼게요. 아까

앞에서 설명드렸던 것처럼 실제로이 30이라는 값을 넣을 거고요.이

0이라는 값은이 0 번째 위치에 넣으라는 거잖아요. 그러면 지금 맨

앞쪽에 넣으라는 거기 때문에 일단 노드를 하나 만들겠습니다. 노드를

하나 만들고 여기에 30이라는 값을 저장을 하고 맨 앞쪽에 넣었기 때문에

이제이 새롭게 만들어진 노드는 헤드가 가르키고 있는이 노드를 가르키도록

해야 돼요. 그래서 이렇게 연결을 시켜 주고요. 그러고 나서 지금 맨

앞쪽에 새로운 노드가 들어왔기 때문에 이제이 헤드도 방금 들어온 새로운

노드를 가르키도록 바꿔 줘야 됩니다. 그래서 이제이 헤드도이 노드를

가르키게 되는 거죠. 자,이어서 어펜드 10을 호출을 하게 되면 또

끝에 붙이는 거잖아요. 그럼 이번에는 빨리 해 볼게요. 또 노드를 하나

만들고 10이라는 값을 넣습니다. 그리고 테일이 가르키고 있던이

마지막에 있던 노드가 방금 만들어진 노드를 가르키게 하고 또 테일을

업데이트 해 줘서 방금 만들어진 노드를 가르치도록 해 줘야 되죠.

자, 이제 어펜드 10이 끝나고 겟 2를 호출를 해 보겠습니다. 그러면은

이건 인덱스인 거잖아요. 그러면 0 1 2 얘의 값을 반환을 해야 되는

건데 지금 얘에 접근하기 위해서는 사실 출발을 어디서부터 해야 되냐면이

헤드에서부터 해야 돼요. 연결 고리가 지금 헤드와 테일밖에 없기 때문에이

헤드에서부터 출발을 해야 모든 노드에 접근할 수 있거든요. 그래서이

헤드에서부터 출발을 해서 이런 식으로 연결된 링크를 따라서 이런 식으로

가서 마침내이 두 번째에 있는이 20이라는 값을 반환을 하게 되는

거죠. 그래서이 개은 이제 20이라는 값을 환하게 됩니다. 지금 그래서

여기서 알 수 있는 것처럼이 링크드 리스트 같은 경우에는 아까 어레이

리스트와는 다르게 어레이 리스트는 인덱스로 바로바로 접근이 가능하지만

얘 같은 경우에는 헤드에서부터 출발을 해서 그 위치까지 이동을 해야

된다라는 그런 시간적 딜레이가 발생한다. 요런게 링크드 리스트의 또

특징 중에 하나인 거죠. 자, 그리고이어서 어펜드 40을 호출 하게

되면 이것도 쉽죠? 이거는 그냥 금방 그림으로 표현하겠습니다. 이런 식으로

동작을 하죠. 그래서 아까 앞에 어레이 리스트 같은 경우에는 사실은이

배열 사이즈가 다 찾기 때문에 더 큰 사이즈에 새로운 배열을 하나 만들고

거기에다 다 복사를 했었어야 되는데 링크드 리스트 같은 경우는 그 과정

없이 그냥 바로이 테일 끝에다가 하나씩 붙여 주면 되는 거죠. 자,

여기서 만약에 테일 없이이 헤드만으로 운영을 했다면이 끝에다가 뭔가를 붙일

때마다 어떻게 해야 되냐면이 헤드로부터 출발을 해서이 끝까지

이동을 해야 돼요. 이렇게 끝까지 이동을 한 다음에 그다음에이 노드를

만들고 새롭게 만들어진 노드를이 마지막 노드가 가르치도록 해야 되는

거거든요. 그래서 테일이 없으면은 항상 끝에 뭘 붙일 때마다 헤드로부터

출발을 해서 그 끝까지 이동을 해야 되기 때문에 이런 시간적 비용 낭비가

있어서 테일을 두는게 더 좋습니다. 자, 아무튼 이제 다음 번 명령을

수행해 보죠. 컨테인즈 50이라는 것을 실행을 했습니다. 그러면이

링크드 리스트에 50이라는 값이 있는지 없는지 확인을 해야 되는

거잖아요. 그러면 여기 헤드에서 또 출발을 합니다. 그래서 헤드로부터

전체 노드들을 하나하나씩 다 확인을 해야 되는 거예요. 50이라는 값을

만날 때까지. 근데 지금 50이라는 값이 하나도 없잖아요. 그러면이

끝까지 다 하나하나 확인을 해서 없다는 것이 검증이 됐으면 비로소

이때이 컨테인즈 50은 포스를 반환하게 되는 거죠. 자, 그리고

이제 리무브 10을 수행을 합니다. 아까 리스트처럼 얘도 일단은 10이

있는지 없는지 찾아야 되잖아요. 10이 있으면 지워야 되고 10이

없으면 지울 수 없을 테니깐요. 그래서 얘도 그러면 처음부터 다시이

헤드에서부터 출발을 해서 하나하나씩 다 확인을 해야 돼요. 그래서 이렇게

하나하나 확인을 했더니 지금 여기서 이제 10이라는 값이 있다는 걸

확인을 했죠. 그러면 이제 어떻게 동작을 하냐면 여기서 삭제하는 것

자체는 쉽습니다. 일단 찾는게 오래 걸리지 일단 찾았으면 그 이후에

삭제는 쉬워요. 그래서 지금이 30일 가르키고 있는이 부분을 이제 연결을

끊어 줘야 되는 거죠.이 연결을 끊어 줘서 이제이 부분은 20이라는 값을

가르치게 됩니다. 그러면 이제 자연스럽게이 링크드 리스트는 이런

식으로 연결이 되는 거죠. 그리고이 친구는 사라지게 됩니다.

이제 마지막으로 리무브라는 동작을 수행해 보겠습니다. 그러면 얘도

마찬가지로이 2번이 2번 위치에 있는 값을 지워 주라는 얘기거든요. 그럼이

노드를 지워 줘야 돼요. 그러면 또이 노드 위치까지 가야 되잖아요. 다시

헤드에서부터 하나하나씩 링크를 타고 여기까지 넘어와야 됩니다. 그래서

삭제해야 되는 위치까지 이동하는데 또 시간이 걸린다는 거 그런 특징이

있고요. 일단 여기까지 오면은 아까 앞에서 봤던 것처럼 집어 주는 거

자체는 어렵지 않죠. 금방 되는 건데 지금 보시면은 이제이 노드가이 노드를

바로 가르치도록 바꿔 주면 될 겁니다. 한번 해 볼게요.요 링크요

링크를 이제 끊어야 되겠죠? 그래서이 링크는 이제 40이라는 값을 가지는

노드를 가르키게 되는 거죠. 그리고 나서 이제이 노드는 자연스럽게 또

사라지게 되는 겁니다. 그럼 최종적으로 이제 링크드 리스트는 이런

형태의 모습이 되겠죠. 어때요? 어렵지 않죠?이 이 링크드 리스트에는

확장 팩들이 있는데요. 서큘러 링크드 리스트가 있고 더블 링크드 리스트가

있고 서큘러 링크드 리스트가 있습니다. 각각이 어떤지 간단하게

살펴볼게요. 먼저이 서큘러 링크드 리스트는이

마지막이 테일이 가르키고 있는 마지막 로드가 가장 앞에 있는 헤드 첫

번째를 가르키게 되는 겁니다.이 테일만 관리하고 있으면이 테일의

넥스트가이 헤드 노드를 가르키게 되기 때문에 이런 경우에는 따로이 헤드라는

포인트를 관리하지 않죠. 테일 하나만으로도 헤드에 바로 접근이

가능하니깐요. 이런 식으로 꼬리와 헤드가 연결되는 형태가 서큘러 링크드

리스트라고 하고요. 이제이 더블리 링크드 리스트는 아까 앞에서 같은

경우에는 일방 통행이었잖아요. 근데 여기는 이제 양방향 통행인 거예요.

이런 경우에는 이제 어느 위치에서건 앞으로 가고 싶을 땐 앞으로 갔다가

뒤로 가고 싶을 땐 뒤로 갈 수 있는 그래서 어느 방향으로든 편하게 갈 수

있어서 좀 더 빨리 접근할 수 있다라는 그런 장점이 있고요. 앞에

두 개를 합친이 설큘러 더블 링크드 리스트 같은 경우에는 지금 보시는

것처럼이 링크드 리스트 헤드와 또 끝에 있는 테일이 서로 연결되는

형태이면서도이 노드들이 각각 앞뒤로 왔다 갔다 할 수 있는 그런 형태의

구조가 되겠습니다. 자, 이제 거의 다 왔는데요. 어레이 리스트와 링크드

리스트를 한번 비교를 해 보겠습니다. 정리하는 차원인 거예요. 자, 먼저이

어레이 리스트와 링크드 리스트를 구현을 보면은요. 거레이 리스트는

베어를 사용을 하고 링크드 리스트는 노드를 연결을 하는 형태로 사용을

합니다. 자, 데이터 접근 시간 같은 경우에는 여기서 이제 데이터

접근이라는 말은 0 번째, 첫 번째, 두 번째, 세 번째 이렇게 접근을 할

때에 어레이 리스트는 배열을 쓰기 때문에 모든 데이터를 상수 시간에

접근 가능하죠.이 링크드 리스트는 몇 번째 위치하는지에 따라서이 이동

시간이 발생을 하죠. 그래서 만약에 헤드에 접근한다면 바로 접근하겠지만

저 뒤쪽에 있는 노드들에 접근을 한다면 그 헤드로부터 혹은 더블리

링크드 리스트라면 테일에서부터 이동을 시켜서 해당하는 위치까지 이동을 해야

된다라는 그런 시간이 추가로 발생을 합니다. 자, 그다음에 삽입 삭제을

살펴보면 둘 다 삽입과 삭제 자체는 상수 시간으로 끝이 나요. 근데 이제

문제는 어레이리스트 같은 경우에는 삽입하거나 삭제할 때에 아까 앞에서

봤던 것처럼 데이터 시프트가 필요할 수가 있거든요. 그런 경우에 이제

추가 시간이 발생할 수 있는 거고 링크드 리스트도 마찬가지로 삽입을

하거나 삭제를 하는 그 위치까지 이동을 해야 되기 때문에 그 위치가

어디냐에 따라서 그 위치까지 이동하는 시간이 발생을 한다는 거 이런 특징이

있고요. 그다음에 리스트 크기를 늘려야 되는 경우에 요거는 링크드

리스트 같은 경우에는 이슈가 없죠. 배열 같은 경우에는 크기가 미리

정해져 있기 때문에 만약에 배열이 다 꽉 차 있는 상태에서 추가로 확장이

필요한 경우 그때는 새로운 배열을 하나 만들고 그 새로운 배열의 기준에

있던 것들을 복사를 해야 되기 때문에 이때 추가 시간이 발생을 한다. 이런

특징이 있고요. 그다음에 각 리스트에서 검색을 할 때 어레이

리스트건 링크드 리스트건 최악의 경우에는 리스트에 있는 아이템들

수만큼 확인을 해야 되는 거죠. 그다음에 CPU 캐시 같은 경우에

어레이 리스트는 배열를 사용하기 때문에 CPU 캐시의 이점을 활용할

수 있지만이 링크드 리스트는 노드 각각이 메모리 공간상에서 띄엄띄엄

떨어져 있기 때문에이 CPU 캐시의 이점을 별로 사용할 수 없다 이렇게

이해를 하시면 될 거 같고요.이 어레이 리스트를 구현하는 예를

살펴보면 자바 같은 경우에는 어레이리스트 같은 이름이죠.

어레이리스트라는 이름의 클래스가 있고요. C파이썬이라고 해서이

파이썬을 구현하는 방법이 여러 가지 방법이 있는데 C 언어로 구현하면

C파이썬이고 뭐 자바 언어로 구현하면 자이썬이라고 하죠. 근데 제가 다른

거는 확인을 못 해 봤고이 C 18선의이 리스트의 구현을 보면은

이게이 어레이 리스트로 구현이 되어 있습니다. 반면에이 링크드 리스트를

구현한 얘는 자바에서는 동명의 링크드 리스트라는 클래스가 있어요. 얘가이

링크드 리스트로 구현이 되어 있다. 그렇게 이해를 하시면 될 것

같습니다. 자, 그러면 올레 리스트와 링크드 리스트에 뭘 써야 되나 이런

이제 고민들이 있을 수 있는데 한 2년 전에 제가 올렸던 영상 보면은

거기에는 이제 장단점이 있으니까 상황에 맞춰서 쓰면 된다 이렇게

설명을 했었는데 이제 그 사이에 저도 성장을 하게 되고 이런저런 공부를

하다 보니까 지금 여기서 설명드렸던 것처럼이 어레이 리스트와 링크드

리스트는 사실 큰 차이가 없거든요. 성능면에서 큰 차이가 없고 특별한

코너 케이스 같은 경우에 뭐 예를 들면은 이런 경우에서는 이제 어레이

리스트가 좀 더 시간적으로 아쉬운 부분이 있지만 또 이런 부분에서는 또

어레이 리스트가 시간적으로 이점을 가져가거든요. CPU 캐시를 활용하기

때문에 좀 더 빨리 처리할 수 있는 거죠. 그리고 또 어레이 리스트의

단점이이 데이터 시프트가 발생할 때, 복사가 발생할 때, 추가적인 시간이

발생하는 부분인데 요것도 많이 튜닝이 되고 최적화가 돼 가지고이 데이터를

복사하는 작업들이 우리가 생각하는 것처럼 뭐 하나하나씩 옮긴다 이런

개념이 아니라 좀 더 빨리 되도록 개선이 된 부분들이 있더라고요.

그래서요 자료 준비하면서 구글링을 좀 더 해 보니까 어레이 리스트랑 링크드

리스트에 뭘 써야 되나 그런 거를 영어로 검색을 해 보시면 생각보다

어레이 리스트를 그냥 써라. 링크드 리스트 말고 그냥 어레이 리스트를

써라. 이런 내용들이 조금씩 있더라고요. 그 제가 모든 언어를 다

확인해 본 건 아니지만 특히 자바 같은 경우에 좀 재밌는 내용이

있었는데이 자바에서 어레이리스트와 링크드 리스트를 뭘 써야 되나 요런

거를 좀 찾다 보니까이 링크드 리스트라는이 자바에 있는이 클래스이

클래스를 구현한 사람이이 조쉬 블로크 어떻게 이름을 읽어야 될지

모르겠지만이 조시 블로크라는 사람이 있는데이 사람이 어떤 글을 남겼냐면

트위터에다가 혹시 링크드 리스트를 실제로 쓰는 사람이 있냐? 내가이

링크드 리스트를 실제로 구현하고 작성하긴 했지만 나도 이거 절대로 안

쓴다. 이런 트위터를 남겼거든요. 그래서이 트위터 따라가 보면 뭐 여러

가지 재밌는 글들이 많아요. 사람들이 댓글 단거 보면 나도 거의 어래

리스트만 쓴다 이런 글들도 많고 뭐 어떤 사람은 퍼스트 인퍼 first

아웃 경우에는 링크드 리스트를 쓴다고 하니까이 사람이 뭐라고 답거를

달았냐면 그런 경우에는 사실 자바에는 AQ가

있다. 얘가 성능이 더 좋다. 이렇게 막 얘기를 써 놓고 있거든요. 그래서

약간 저는 생각이 바뀌었어요. 이제 제 개인적인 생각이거든요. 이거는

여기서 이제 자바에 한정된 얘기긴 하지만 어쨌든 어레이 리스트를 쓰는게

더 좋다 그렇게 생각을 합니다. 그리고 자바 말고도 사실 구글링을 좀

해 보시면 뭐 예를 들면 시불이었나요? 하여튼 그 실불 가지고

퍼포먼스 비교한 뭐 데이터들도 있고 여러 가지 퍼포먼스 비교한 것들이

있어 가지고요. 그래서 재미사만 한 번씩 찾아보시면 될 거 같아요. 자,

오늘 영상은 이제 여기까지고요. 드디어 우리 채널도 구독자가

500명이 돌파를 했습니다. 500명이면 정말로 큰 숫자잖아요.

많은 숫자라고 생각을 하는데 사실 자막도 없고 좀 재미 없을 수도 있는

영상을 그래도 많이 찾아 주시고 봐 주셔서 감사하다는 인사를 드리고

싶었습니다. 앞으로도 계속해서 좋은 영상으로 찾아뵐 수 있도록 저도 더

열심히 노력을 할게요. 자, 그러면 또 다음 영상을 저는 준비하러가

봐야겠죠? 끝까지 봐주신 여러분들 정말 최고시고요. 앞으로도 계속해서

잘 부탁드리겠습니다.