[자료구조] 리스트(List) - 코딩밥상

리스트의 개념

이름에서 유추할 수 있듯이 리스트 목록 형태로 이루어진 데이터 형식입니다.

노드 목록에서 첫 번째 노드는 헤드(Head),마지막 노드를 테일(Tail)이라고 부르는데, 따라서 리스트의 길이는 헤드부터 테일까지의 노드의 개수가 됩니다.

---

리스트 ADT

• 리스트에 노드를 추가하는 추가 연산(Append)
• 노드 사이에 노드를 삽입하는 삽입 연산(Insert)
• 리스트에 있는 노드를 제거하는 제거 연산(Remove)
• 특정 위치에 있는 노드를 반환하는 반환 연산(GetAt)

---

리스트와 배열의 비교

배열은 리스트처럼 데이터 목록을 다루며, C언어에서 기본적으로 제공하기 때문에 프로그래머가 따로 구현하지 않아도 된다는 장점이 있습니다. 하지만 배열은 생성하는 시점에서 반드시 배열의 크기를 지정해줘야 하고 생성 후에는 그 크기를 변경할 수 없다는 한계점이 있습니다.

즉 생성과 함께 크기가 제한되는것이죠. 너무 작게 선언하자니 일을 수행하지 못하고, 너무 크게 선언하자니 메모리를 낭비하는 일이 발생하기 쉽상입니다.

배열처럼 데이터 집합 보관 기능을 가지면서 위의 문제들을 해결하기 위한 자료구조가 '리스트(List)'입니다.

즉 배열과 다르게 노드를 추가/제거 하면서 그 크기를 기능에 맞게 조절할 수 있는것이죠.

---

구현 방법

리스트의 대표적인 구현 방법으로는 링크드 리스트 그 방법에서도 싱글 링크드 리스트(SLL), 더블 링크드 리스트(DLL), 환형 링크드 리스트(CLL)이 있습니다.

다음 3개의 구현은 다음 포스팅에서 자세히 다뤄보겠습니다.

 

2022.12.22 - [자료구조/리스트(List)] - [자료구조] 싱글 링크드 리스트(Singly Linked List / SLL)

[자료구조] 싱글 링크드 리스트(Singly Linked List / SLL)