[자료구조] 연결리스트

이정우·2023년 3월 6일
0

자료구조

목록 보기
2/5
post-thumbnail

밸하!

밸로그 여러분 안녕하세요

오늘은 연결리스트에 대해서 작성을 해보려고합니다

1. 정의

연결리스트란?

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조 입니다
각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구분이 됩니다

그럼 이 연결리스트가 어떤 특징을 가지고 있는지 알아보겠습니다!

연결리스트의 특징

연결리스트는 배열과 차이점이 있습니다
바로 연결리스트는 제한없이 요소를 동적으로 추가해 나갈 수 있다는 것입니다!

그리고 배열과는 다르게 탐색에 선형시간 O(n)이 들어갑니다.
그리고 요소를 추가 또는 제거를 할 때 O(1)의 시간 곧 상수시간이 소요되게 됩니다.
이것만 보더라도 배열과 반대라는것을 알 수 있습니다.

연결리스트의 구현 방법은 세가지가 존재하는데
Singly Linked List/ Doubly Linkd List/ Circular Linked List 가 존재합니다.

각각 단일연결 리스트, 이중연결리스트, 환형 연결리스트라고도 부릅니다!

그럼 이제는 배열과 연결리스트의 차이에 대해서 알아보겠습니다!

배열과 연결리스트의 차이

첫번째로, 메모리에서의 차이가 있습니다

먼저, 배열은 순차적으로 데이터를 넣어주기에 메모리를 순차적으로 사용하게 됩니다
하지만 연결리스트는 순차적이지 않기에 각 데이터가 퍼져있습니다!
연결리스트는 퍼져있는 메모리영역을 알기위해 포인터를 사용하여 각 영역을 참조하게 됩니다!

그다음으로는 추가와 삭제적인 측면에서 보겠습니다
배열은 요소를 추가와 삭제를 하려면 선형시간 O(n)의 시간이 필요합니다
그 이유는 삭제된 요소의 공백을 메꾸기 위해서 뒤에 있는 요소들을 앞으로 당겨야하기 때문입니다!
뿐만 아니라 배열의 요소를 중간에 추가하기 위해서라면 뒷요소를 한칸씩 뒤로 미뤄야 하기 때문입니다!

하지만,
연결리스트의 요소의 추가와 삭제는 차이가 있습니다
먼저 연결리스트에서의 삭제에 대해서 알아보겠습니다
연결리스트에서 요소를 삭제할 때는 단순히 삭제할 요소 앞에있는 요소의 포인터를
삭제할 요소 다음의 요소에 연결해주면 됩니다.
이후 삭제할 요소를 완전히 삭제해주면 연결리스트의 삭제 로직이 끝나게 됩니다

즉, 배열의 방식과는 다르게 단순히 포인터의 연결만 바꿔주면 되기에 걸리는 시간 또한도
상수시간 O(1)만 걸리게 됩니다

그 다음으로는 연결리스트의 추가를 한번 보겠습니다
연결리스트의 추가는
추가할 요소의 포인터를 추가할 요소의 다음 요소에 연결시켜줍니다.
이어서 추가된 요소의 이전 요소의 포인터를 추가된 요소에 연결시켜주면 로직이 끝나게 됩니다
이런 방식이니 추가 또한도 상수시간만 소요가 됩니다!

그럼이제 3가지 연결리스트 하나씩 알아보겠습니다!

1.Singly Linked List (단일 연결 리스트)

단일 연결리스트는 가장 기본적인 연결리스트입니다!
단일 연결리스트는 단순히 Head에서 Tail까지 단방향으로 이어지는 연결리스트 입니다!
여기에서 Head는 가장 첫번째 요소를 의미하고 Tail은 가장 마지막 요소를 의미합니다!

tail요소에는 포인터 영역이 NULL로 표시가 됩니다
즉 더이상 갈곳이 없다는것을 의미합니다

연결리스트에는 핵심로직이 있습니다!

바로
-요소 찾기
-요소 추가
-요소 삭제

가 있습니다!

요소 찾기

연결리스트에서 요소를 찾으려면 어떻게 해야할까요~??

먼저 Head포인터에서 시작을 해서 다음포인터의 head를 찾습니다 그다음 요소가 우리가 찾는 숫자인지 확인하고 아닌경우 다음요소로 포인터를 통해서 넘어가게 됩니다

이 과정을 반복하게 됩니다!

이 때 우리가 원하는 요소를 찾았다면 로직이 종료가 되게 됩니다

그 다음은

요소 추가

바로 요소 추가입니다!

연결리스트에서 요소를 추가하려면 어떻게 해야할까요~??

먼저 첫번째로 추가할 요소의 포인터를 그다음에 들어갈 요소의 데이터를 가지고있는 부분을 향하게 합니다
그다음 앞에 위치할 요소의 포인터를 추가할 요소의 데이터를 가지고 있는 부분을 향하게 합니다

이 로직은 단순하기에 O(1)의 시간만이 소모되게 됩니다
단 상수시간이 걸리는 것은 요소를 추가/삭제할때만 해당이 됩니다

요소를 탐색하거나 가리켜야하는 데이터의 요소를 탐색한다면
탐색 로직이 있어야하기에
O(n) 선형시간이 소요되게됩니다!

여기서 주의할 점이 생기는데요

*추가를 하기위해서 탐색을 하는 로직을 작성하지 않게 주의해야합니다

마지막은

요소 삭제

마지막은 요소 삭제입니다

요소 삭제는 요소 추가와 비슷합니다

먼저 삭제해야할 요소의 앞의 요소의 포인터를
삭제 해야할 요소 다음의 데이터를 가리키게 합니다
그 다음 삭제할 요소를 메모리상에서 제거합니다!

정말 간단하죠??

간단한 만큼 상수시간만이 소요가 되게 됩니다!

그다음은

2. Doubly Linked List(이중 연결 리스트)

입니다!

이중 연결리스트는 단일 연결리스트와는 다르게 포인터를 두개를 가지고 있습니다

즉 다음과 이전을 가리킬 수 있어 이전과 다음을 가리킬 수 있게됩니다!

포인터를 두개를 가지고 있기 때문에 단일 연결 리스트보다 자료구조의 크기가 조금 더 크게 됩니다!

그럼 이중 연결 리스트는 어떻게 요소 추가를 할까요??

단일 연결리스트 보다는 조금 복잡하지만 그렇게 어렵지는 않습니다!

요소 추가

먼저 요소 추가 입니다!

먼저 포인터가 추가할 요소의 다음요소를 가리키게 만듭니다!
이어서 추가할 요소의 이전 요소의 포인터가 추가할 요소의 데이터를 가리키게 만듭니다
이후 추가할 요소의 다음 요소의 두번째 포인터를 추가할 요소를 가리키게 만듭니다

마지막으로 추가할 요소의 두번째 포인터를 추가할 요소의 이전 요소를 가리키게 만들면

요소 추가 로직이 끝이나게 됩니다!

이렇게 간단하기에

요소 추가 로직은 단일 연결 리스트와 같이 O(1) 상수시간만이 소요되게 됩니다!

요소 삭제

그다음은 요소 삭제입니다!

요소 삭제도 요소 추가와 비슷하게 진행이 되는데요

먼저 삭제할 요소의 앞의 요소의 포인터가 삭제할 요소의 다음요소의 데이터 영역을 가리키게 합니다
이후 삭제할 요소의 다음 요소의 두 번째 포인터 영역을 삭제할 요소의 이전 요소를 가리키게 해주면 됩니다!
그후 삭제할 요소를 메모리에서 제거해주면 됩니다!

이렇게 요소 삭제 또한도 요소 추가와 같이 O(1)상수 시간만이 소요가 됩니다!

마지막으로

3. Circular Linked List(환영 연결 리스트)

입니다!

환영 연결리스트는 사실 한가지만 제외하면 단일 또는 이중 연결리스트와 동일합니다! 그렇기에 로직도 큰 차이가 없습니다!

그럼 어떤 것이 다를까요??

바로 리스트의 tail곧 마지막부분의 포인터가 첫번째 요소의 포인터를 가리키게 한다는 차이점이 있습니다!

이렇게 원처럼 연결이 되어있기 때문에 중간에서 탐색을 시작하더라도 전부다 탐색을 할 수가 있습니다

자 이렇게 오늘은 자료구조중 한개인 연결리스트에 대해서 알아보았는데요!

자료구조를 한개씩 공부하면서 로직을 어떻게 작성할지 고민해보는 좋은 시간이었던것 같습니다!

그럼 이만
밸~바!

profile
주니어 프론트엔드 개발자

0개의 댓글