네 반갑습니다 오늘 이 영상을 끝까지 보신 후에 ADT 에서 리스트에 대한 개념과 그리고  EST 에 구현된 어레이 리스트, 링크드 리스트를 이해하게 됩니다. 자, 그럼 오늘도 고고씽! 자, 그럼 먼저 ADT 의 관점에서 리스트를 한번 살펴볼게요. 이 리스트

라는 것은 값들을 저장하는 추상 자료형 입니다. 이 리스트는 특징 있는데요, 일단 순서가 있구요. 그리고 중복을 허용을 합니다. 자, 그래서 이

리스트는 언제 쓸 수 있나? 이런 경우에 쓸 수 있겠죠. 객관식 문제의 정답을 저장해야 될 때 이럴 때

리스트를 쓸 수 있을 겁니다. 지금 오른쪽에 보시면 2번까지 문제가 있거든요. 4지선다형으로 2번까지

문제가 있는데 200개의 문제에 대해서 다 정답 값들이 있을 거잖아요. 그럼 이 정답들을 리스트에 관리할 수 있는 거죠. 그러면 이 정답에는

순서가 중요하니까 순서대로 차근차근 각 정답들을 저장을 할 거구요 똑같은 정답이 지금 보면 4지선다형이기

때문에 각 정답들이 이제 중복이 될 수가 있겠죠 그래서 이런 경우에 리스트에 딱 저장을 하면 좋을 것 같다는 생각이 들구요

그러면 리스트는 또 언제 쓸 수 있을까요 이런 경우에도 쓸 수 있겠죠 일반적으로 사용되는 프로그래밍 언어

순위를 저장하고 싶을 때도 리스트를 사용할 수 있을 겁니다 지금 오른쪽에 보시는 자료는 2021년 스택 오버플로우에서 개발자들에게

설문조사한 결과인데요 지금 보시면 자바스크립트가 제일 자주 사용되는 언어로 뽑혔고 세 번째, 여덟 번째, 다섯 번째

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

리스트를 사용할 수 있겠죠 물론 지금 이 경우에는 탑들이 중복될 일은 없을 거에요 바로 앞에 봤던 예

랑은 다르게 값들 자체가 중복될 일은 없겠지만 랭킹을 순서대로 저장을 해야 되기 때문에 이런 경우에는 리스트가

또 적절한 거죠 자 이것 말고도 리스트는 언제 쓸 수 있을까요 추후 영상에도 다루게 되겠지만 이

셋이나 맵을 사용하는 게 더 적절한 상황이 아니라면 일반적으로 거의 대부분은 리스트를 사용한다고 봐도

무리가 없을 것 같아요 가령 티비에서 데이터를 읽어 왔을 때 만약에 여러 개의 데이터를 읽어 본다면 그 여러 개의 데이터를 어디에 담아야 되잖아요

그러면 만만한 게 리스트이기 때문에 이런 경우에도 리스트를 사용하게 되거든요 이런 식으로 셋이나 맵을 사용하는 게 더 적절한 상황이 아니라면

리스트를 쓰면 된다. 그렇게 이해를 하시면 될 것 같아요. 자, 그러면 이제 본격적으로 이 리스트에 구현체를 살펴볼게요. 앞에

설명은 ADT 관점에서 살펴본 거라면 이제는 이 리스트를 실제로 구현하는 방법들을 살펴보는 거죠. 1. 리스트

구현체에는 대표적으로 2가지가 있는데요. 하나는 어레이 리스트가 있고 하나는 링크드 리스트가 있습니다. 먼저 어레이 리스트부터 살펴보면

이 어레이 리스트는 배열을 사용해서 리스트를 구현하는 방식입니다. 그래서 예를 들어서 이만한 크기의 배열을 하나 잡아놓고 그 안에다가 이런 식으로

데이터를 차곡차곡 저장을 하는 거죠. 그러면 이 어레이 리스트가 어떻게 동작하는지 본격적으로 여러 가지 동

작들과 함께 살펴보도록 할게요. 여기에 있는 이 동작들은 그냥 제가 임의로 이름을 붙인 거라서 이 각

프로그램이 언어마다 내 3rd 파라미터나 함수 이름은 조금씩 다를 수가 있어요. 자, 어쨌든 그럼 하나하나 한번 실행해

보겠습니다. 먼저 어펜드 10이에요. 그러면은 지금 이 배열이 크기가 4개짜리인 배열이 1 잡혀 있는 거잖아요. 그러면 여기에 어펜드 12

니까 아직 아무것도 없기 때문에 맨 앞쪽에 11 넣습니다. 그리고 어펜드 20을 하면 이제 끝쪽에 계속

채우는 거거든요. 그러면 그 다음 짜리에 20을 넣어요. 그리고 여기서 이제 인서트를 하게 되는데 인서트

를 보시게 되면 지금 두 가지 파라미터가 있는데 1, 4, 0이고 1, 30이거든요. 그러면 값을 30이라는 값을 넣을 건데 이 앞에 1

은 뭐냐면 0번째 인덱스에 30을 넣을 거다라는 의미에요. 그 말은 무슨 말이냐면 지금 이 위치에 30일

넣겠다는 건데 지금 22라는 값이 있기 때문에 오른쪽으로 데이터들을 다 시프트를 시켜줘야 돼서 그럼 이제

시프트를 지켜보겠습니다 이렇게 하나하나 시프트를 하게 되면 이제 여기에 22 들어가게 되고 원래 22

있던 자리에는 이제 12 들어가게 되죠 그리고 이제 이 원래 12 있던 자리에 32 들어가게 됩니다 그래서 지금 보시는 것처럼 이 어레이

리스트에 값을 넣게 되면 그 공간을 마련하기 위해서 데이터 시프트가 일어난다 그만큼 시간이 좀 더 딜레이 된다 그렇게 이해를 하시면 될 것

같구요 다시 그러면 이어서 쭉 실행을 해 보겠습니다 이제 어펜드 12라서 이제 끝자리에 또 10을 얻는 거죠

그리고 이제 get 2를 호출합니다 이것은 뭐냐면 인덱스 이번 위치에 있는 값을 가져오라는 거군요 그럼

인덱스는 우리가 이전 영상에서 배웠던 것처럼 지금 배열이니까 인덱스는 0부터 시작을 하죠. 그래서 0, 1

이면 지금 여기 위치에 있는 값을 가지고 오라는 그런 요청이기 때문에 이제 이렇게 될 일을 하게 되며 얘는 20이라는 값을 반환을 하게 되는

거죠. 자 그리고 나서 이제 다시 또 어펜드 42 호출이 됐습니다. 그런데 지금 공간이 없잖아요. 이제 더 이상

넣을 공간이 없어요. 꽉 차 있기 때문에 그럼 이때 이제 어떻게 동작을 한다면 지금 현재 크기가 4개짜리 인

배열보다 더 큰 배열을 1 만들어요. 지금은 예를 들어서 그냥 8개짜리를 만든다 하겠습니다. 이렇게 8개짜리를 만들구요.

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

이제 이 자리에 이제 40을 넣게 되는 거죠 이해가 되시죠 그리고 나서 이제 얘는 뭐 이제 더 이상 사용하지

않게 되는 겁니다 자 이제 계속 다시 이어서 실행을 해 볼게요 이제 컨테이너 52 고추 됐습니다 이 말은 이 어레이 리스트에 50 이라는 값이

있으면 프로를 2000 하고 없으면 홀스 를 리턴하는 의미 거든요 그러면 이때 이제 어레이 리스트에서 이 0번째

부터 차근차근 1 다시 확인 합니다 0 번째부터 이렇게 쭉 확인해요 근데 지금 50 이라는 값이 올해 일일

수도 없기 때문에 전체 지금 아이템의 5개가 있는데 이 5개를 다 확인해도 없었기 때문에 이때는 이 컨텐츠가

볼스 를 2000 하게 되겠죠 자 이처럼 뭔가를 찾을 때 탐색하게 될 때는 최악의 상황에 는 이 어레이

리스트에 있는 모든 아이템들을 한번씩 확인해 봐야 된다 이런 특징 있다는 것을 또 이해를 하시면 됩니다.

자 이어서 다음 동작을 수행해 봅시다 이 제거 부분을 하게 되는데 이것은 무슨 말이냐면 어레이

리스트에서 12 있으면 그 값을 지워 2 라는 얘기 거든요 그러면 여기도 일단 10 을 찾아야 돼요 이어 레이 리스트에 12

없을 수도 있으니까 일단 10 을 찾아야 되잖아요 그러면 마찬가지로 아마 대부분의 프로그래밍 언어가

비슷할 텐데 앞에서부터 찾거든요 그러면은 여기를 먼저 확인합니다 그다음 여기를 확인해요 근데 지금

12 있잖아요 그럼 이제 이 친구를 이제 키워 줘야 되는 거죠 22 라는 친구를 치고 두게 되며 이제 이

공간이 비게 되잖아요 그러면 이 공간을 또 메꿔 줘야 돼요 그래서 이 공간을 메꾸기 위해서다 또 이렇게

새 팩트가 발생을 해야 됩니다 그래서 20을 앞으로 한 칸 땡기고 마찬가지로 원래 22 있던 자리에 10을 써 주게 되구요 원래 12

있던 자리에 40을 써 주게 되며 그리고 원래 42 있던 자리는 이제 지워 주게 됩니다 자 그리고 이제 마지막 동작을 한번 해볼게요

지금 이 마지막 동작은 이 무브 옛 이라고 되어 있는데 이거는 인덱스로 이번 이번 위치에 있는 값을 지워 주는 얘기 있거든요 그럼 얘도

똑같아요 이번 위치에 있는 값을 일단 지워 주고 또 시프트를 해줘야 돼요 빈 공간을 메꿔야 되니깐 그러면은 이

42라는 값이 앞으로 또 이렇게 옮겨 줘야 되겠죠 그러면 이제 이 위치에 42가 들어가고 기존의 42

있던 위치는 또 비워 줘야 됩니다. 그래서 최종적으로 이런 모습이 되는 거죠. 자, 이런 식으로 월에 리스트가 동작을 한다 이해를 하시면 될 것

같습니다. 그럼 이번에는 링크드 리스트에 대해서 살펴볼게요. 링크드 리스트는 노드를 연결시킨 형태로 구현이 돼요. 지금

밑에 보시는 이런 것들이 있잖아요. 이런 것들 하나하나가 다 노드고요. 이 노드의 보면 값을 저장하는

공간이 있고 그 다음에 다음 노드를 가리키는 포인터, 혹은 레퍼런스를 저장할 위치가 또 따로 있거든요.

그래서 노드들이 서로 연결이 되어 이런 식으로 앞에 노드가 그 다음 노드를 가르치고 또 그다음 노드는

마찬가지로 값을 저장할 위치가 따로 있고 다음 노드를 가리키는 레퍼런스를 따로 저장하고 있어서 그래서

라스가 또 다음 노드를 가르치고 이런 식으로 동작을 하게 되는 겁니다 그리고 가장 끝에 있는 노드는 가르치는 게 더 이상 없기 때문에 이제

자바로 치면 널, 아무것도 가리키는 게 없다는 뜻의 그 널 값을 가지게 되는 거죠 그리고 이 링크드

리스트는 처음 부분을 가리키는 헤더라는 게 있고 리스트의 마지막 노드를 가리키는 2q 일이라는 또 레퍼런스

들이 이렇게 가까이 있다고 이해를 하시면 되겠습니다 사실 이 링크드 리스트랑 어레이 리스트의 가장 큰 차이는 메모리

어떻게 저장되는가 이 차인데요 아까 어레이 리스트 같은 경우에는 배열을 쓰기 때문에 배열은 앞선 영상에서 살펴보았던 것처럼 연속적인 메모리

공간에 데이터를 저장하는 거라면 링크드 리스트는 모두 각각 이 각 포인터를 통해서 다음 노드를 가리키는 형태로 관리가 되기 때문에 이 메모리

공간 상에서 따로따로 이렇게 띄엄띄엄 저장이 된다고 이해를 하시면 될 것 같아요 그래서 지금 보시면은 이

친구가 이 메모리 상에서 따라가면 이 엑스트라는 p 2 레퍼런스가 결국은 다음번 노드를 가리킨다고 했죠

그러면 그 메모리 어딘가에 있는 다음번 노드를 가르치게 되고 그 다음 포인터 역시도 넥스트라고 표시된 인해

플러스를 통해서 메모리 어딘가에 있는 또 다음 노드를 이런 식으로 가르치게 되는 거죠 그래서 핵심은 메모리

상에서 링크드 리스트가 이런 형태로 저장이 된다 그렇게 이해를 하시면 될 것 같아요 자 그러면 이 링크드 리스트도 이런

여러 동작에 따라서 어떤 식으로 변화가 일어나는지 살펴보도록 할게요 자 기본적으로 먼저 어헤드라는 이

링크드 리스트의 첫 번째 노드를 가리키는 이 헤드라는 걸 하나 만들어 놓구요, 헤드 하나만

죽어도 구현할 수는 있습니다만 이번에 같은 경우에는 테일도 같이 사용하도록 하겠습니다. 그래서 테일은 링크드 리스트의 마지막 노드를

가리키는 거죠. 현재 이 헤드와 테일이 가리키는 것은 아무도 없는 상태에서 이제 앱펜드 10으로 호출하면 어떤

식으로 동작을 하느냐. 일단 노드를 하나 만들죠. 또 노드를 하나 만들고 이 노드의 값을 10으로 넣습니다.

지금 현재 이 노드가 가리키는 다음번 노드는 아무것도 없는 상태기 때문에 따로 화살표를 표시하지 않겠습니다.

그리고 이제 헤드 값에 방금 만들어진 이 노드를 가리켜야 되겠죠. 자 이 상태에서 이제 앱펜드 20을

하게 되며 꼬리에 하나를 붙이는 거잖아요 그러면 일단 노드를 하나 또 새로 만듭니다 22라는 값을 저장하는 노드를 하나

새로 만들고 이제 꼬리에 붙이는 거기 때문에 기존의 이 테일을 가리키고 있던 이 노드 이 노드가 이제 방금

만들어진 20이라는 값을 가지는 노드를 가르치도록 만들어 줘야 돼요 그리고 나서 이제 테일이 방금 붙은 20이라는 노드를 또 가리키도록

바꿔 줘야 되겠죠 그러면 이제 테일은 새로 만들어진 노드를 가르치게 됩니다 자 이 상태에서 이제 또 엔 썰 트

0 30을 해볼게요 아까 앞에서 설명 드렸던 것처럼 실제로 이 30이라는 값을 넣을 거구요 이 영희라는

값은 20번째 위치에 넣으라는 거잖아요 그러면 지금 맨 앞쪽에 있는 거기 때문에 일단 노드를 하나

만들겠습니다 노드를 하나 만들고 여기에 30 이라는 값을 저장을 하고 맨 앞쪽에 넣었기 때문에 이제 새롭게 만들어진

노드는 헤드가 가리키고 있는 이 노드를 가리키도록 해야 돼요 그래서 이렇게 연결을 시켜 주고요 그리고

나서 지금 맨 앞쪽에 새로운 노드가 들어왔기 때문에 이제 헤드도 방금 들어온 새로운 노드를 가리키도록 바꿔

줘야 된다 그래서 이제 헤드도 이 노드를 가리키게 되는 거죠 자 이어서 어펜드 10 을 호출하게 되면

또 끝에 붙이는 거잖아요 그럼 이번에는 빨리 해볼게요 또 노드를 하나 만들고 10 이라는 값을

저장합니다 그리고 테일이 가리키고 있다 이 마지막에 또 노드가 방금 만들어진 곳으로 가르치게 하고 또 테일

업데이트 해 줘서 방금 만들어진 노드를 가리키도록 해 줘야 되죠 자 이제 어펜드 12 끝나고 get D를 호출해

보겠습니다 그러면 이건 인덱스 인 거잖아요 그러면 0 1 2 예 값을 반환을 해야 되는 건데 지금 예제 접근하기 위해서는 사실 출발을

어디서부터 해야 되냐면 이 헤드에서 붙어야 돼요 연결고리가 지금 헤드와 tail 밖에 없기 때문에 이 헤드에서

부터 출발해야 모든 노드에 접근할 수 있거든요 그래서 헤드에서부터 출발을 해서 이런 식으로 연결된 링크를

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

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널


쉬운코드

리스트 ADT 개념 소개 및 활용 예시

리스트는 값들을 저장하는 추상 자료형으로 순서가 있으며 중복을 허용한다.

객관식 문제의 정답 저장에 활용 가능하다.

프로그래밍 언어 순위 저장에도 적합하다.

셋이나 맵보다 적절하지 않은 상황이 아니라면 대부분 리스트를 사용한다.

TV에서 여러 개의 데이터를 읽어올 때 임시 저장소로 사용 가능하다.

배열을 사용하여 리스트를 구현한다.

append 연산은 배열의 끝에 데이터를 추가한다.

insert 연산은 특정 인덱스에 데이터를 추가하며, 데이터 시프트가 발생한다.

get 연산은 특정 인덱스의 데이터를 가져온다.

배열이 가득 차면 더 큰 배열을 생성하고 기존 데이터를 복사한다.

contains 연산은 특정 값이 존재하는지 확인하며, 최악의 경우 모든 아이템을 확인해야 한다.

remove 연산은 특정 값을 제거하며, 데이터 시프트가 발생한다.

move 연산은 특정 인덱스의 값을 제거하며, 데이터 시프트가 발생한다.

노드를 연결하여 리스트를 구현하며, 각 노드는 값과 다음 노드를 가리키는 포인터를 갖는다.

어레이 리스트와 달리 메모리 공간에 연속적으로 저장되지 않는다.

append 연산은 새로운 노드를 생성하여 리스트의 끝에 추가한다.

insert 연산은 새로운 노드를 생성하여 특정 위치에 추가한다.

get 연산은 헤드 노드부터 시작하여 특정 위치의 노드를 찾아 값을 가져온다.

contains 연산은 헤드 노드부터 시작하여 특정 값을 찾는다.

remove 연산은 특정 값을 가진 노드를 찾아 제거한다.

removeAt 연산은 특정 인덱스의 노드를 제거한다.

싱글 링크드 리스트, 더블 링크드 리스트, 순환 링크드 리스트가 있다.

어레이 리스트와 링크드 리스트 비교 및 결론

어레이 리스트는 배열을, 링크드 리스트는 노드 연결을 사용한다.

데이터 접근 시간은 어레이 리스트가 상수 시간, 링크드 리스트는 위치에 따라 변한다.

삽입/삭제 시간은 둘 다 상수 시간이지만, 어레이 리스트는 데이터 시프트, 링크드 리스트는 위치 이동 시간이 발생할 수 있다.

리스트 크기 확장은 링크드 리스트가 유리하다.

CPU 캐시 활용은 어레이 리스트가 유리하다.

성능 면에서 큰 차이가 없으며, 상황에 맞게 선택하면 된다.

많은 경우 어레이 리스트 사용을 권장하는 경향이 있다.