[자료구조] 선형 리스트(Linear List)와 연결 리스트(Linked List)

🐣 리스트(List)

---

오늘은 리스트(List)에 대해서 살펴보겠당! 앞에서 살펴본 것과 같이! 자료 구조는 데이터를 연속적으로 연결한 '선형 구조'와 데이터를 비연속적으로 연결한 '비선형 구조'로 나뉜다. 선형 구조 중에 하나인 리스트에 대해서 살펴볼건데, 이는 '선형 리스트'와 '연결 리스트'로 나눠서 살펴볼 수 있다!_! 오늘도 레츠꽁!

 

 

아래는 자료 구조의 개념과 전체 틀에 대해서 설명하여 정리한 글! 참고하기

[자료구조] 선형구조와 비선형구조

 

🐣 선형 리스트(Linear List)

---

1. 개념

선형 데이터 구조에서 데이터 요소는 순차적 순서로 배열되며, 각 요소는 이전 및 다음 인접 요소에 연결. 이 구조를 사용하면 데이터를 직접 탐색 가능. 삽입, 삭제, 액세스와 같은 일반적인 작업은 일반적으로 순차적으로 수행.

 

 

2.  특징

• 배열과 같이 연속되는 기억 장소에 저장되는 리스트
• 선형 리스트의 대표적인 구조는 배열(Array)
• 가장 간편한 자료구조, 접근 구조 빠름
• 자료의 삽입, 삭제 시 기존 자료의 이동 필요

 

3.  배열(Array)

• 배열은 인덱스나 키로 식별되는 요소의 모음
• 모든 요소는 동일한 데이터 유형을 가지며 인접한 메모리 위치에 저장
• 액세스 시간은 일정하지만(O(1)) 삽입 및 삭제에는 비용이 많이 들 수 있음

 

 

🐣 연결 리스트(Linked List)

---

1. 개념

연결리스트는 각 노드가 데이터와 다음 노드에 대한 참조(또는 링크)를 포함하는 일련의 노드. 단일 연결(각 노드가 다음 노드를 가리킴) 또는 이중 연결(각 노드가 다음 노드와 이전 노드를 모두 가리킴). 위치를 알고 있으면 삽입과 삭제가 효율적이지만(O(1)), 액세스 시간은 선형(O(n)).

 

2. 특징

• 노드의 포인터 부분으로 서로 연결시킨 리스트
• 연결하는 방식에 따라 '단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트'로 구분
• 노드의 삽입, 삭제가 선형 리스트와 달리 편리
• 연결을 위한 포인터가 추가되어 저장 공간 추가로 필요
• 포인터를 통해 찾는 시간 추가되어 선형 리스트에 비해 느림

 

3. 노드(Node)와 포인터(Pointer)

노드(Node)

데이터 저장 부분과 포인터 부분으로 구성된 저장 공간

 

포인터(Pointer)

현 위치에서 다음 위치를 알려주는 요소

 

(참고) 링크와 포인터의 차이

'포인터 = 링크'라고 생각하기. 노드들이 포인터로 연결되었다는 표현은 링크(구현을 위한 문법 -> 포인터) 라고 생각.

포인터는 메모리 공간 주소를 가리키는 변수. Java나 python 등에서는 포인터 사용하지 않고 자동 할당 해주기 때문에 좀 더 정확하게 표현하면 '노드 = 데이터 + 링크'라고 할 수 있음

 

 

🐣 비교하기

---

대표적인 구조

선형 리스트	연결 리스트
배열(Array)	노트(Node)

 

삽입 삭제

선형 리스트	연결 리스트
기존 자료 이동 필요	편리

 

용량

선형 리스트	연결 리스트
더 적은 용량	포인터 추가로 저장 공간 추가 필요

 

접근 구조 

선형 리스트	연결 리스트
더 빠르게 접근	포인터를 통해 찾아 선형 리스트에 비해 느림

 

---

다음은 스택, 큐, 데크를 알아보자!

[자료구조] 스택(Stack), 큐(Queue), 데크(Deque)