[자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List)

연결 리스트는 *노드(Node)의 연결로 이루어진 자료구조이다.

*노드 : 연결 리스트에서 데이터를 구성하는 요소(데이터, 연결 정보(링크)로 구성되어 있음)

https://reakwon.tistory.com/25

노드는 데이터(data)와 다음 노드를 가리키는 링크(next)로 구성되어 있다.

제일 앞에 있는 노드를 헤드(head), 제일 끝에 있는 노드를 테일(tail)이라고 한다.

 

연결 리스트의 장단점

📌 장점

연결 리스트의 가장 큰 장점은 리스트의 길이가 가변적이라는 것이다.

배열은 크기가 가변적이지 않아서 크기를 정해준 다음에 부족하면 메모리를 더 할당하고, 배열의 데이터를 복사해야 한다.

하지만 연결 리스트는 다음 노드만 추가하면 되기 때문에 리스트의 사이즈를 조정하는 데 큰 비용을 들이지 않는다.

 

📌 단점

연결 리스트는 어떤 노드를 검색하거나 데이터를 변경할 때 바로 찾아낼수가 없다. 최악의 경우 연결 리스트의 모든 노드를 전부 탐색해야 할 수도 있다.

 

연결 리스트는 언제 사용될까?

📌 음악 들을 때

자신의 플레이 리스트에서 자동으로 다음 음악이 재생될 때 사용된다!

 

📌 방문한 웹 페이지 리스트

실제 stack이나 queue를 구성하는데도 연결 리스트를 활용 한 것!

 

배열 VS 연결 리스트

🎲 input size(얼마나 들어오는지) 모르는 상황 : 배열 < 리스트

유동적으로 메모리 할당을 조절할 수 있는 리스트가 더 유리하다.

 

📚 중간 데이터를 추가, 삭제할 때 : 배열 < 리스트

배열의 경우에는 중간에 값을 추가하거나 삭제하게 되면 인덱스 번호를 전부 당기거나 한 칸씩 뒤로 이동시켜주어야 한다. 하지만 리스트의 경우는 링크의 연결만 바꿔주면 되기 때문에 더 유리하다.

 

📃 데이터의 검색 : 배열 > 리스트

배열은 인덱스를 지정해서 값을 찾으면 되기 때문에 빠르지만 리스트는 하나씩 찾아야 한다.

 

주로 데이터의 탐색을 위한 것이라면 배열을 쓰는 것이 좋고

데이터가 자주 추가되거나 가변적으로 자주 변하게 될 프로그램이라면 연결 리스트를 사용하는 것이 좋다.

 

실습

사실 리스트라는 자료구조는 구현 방법에 따라 크게 두 가지로 나뉜다. (⭐연결 리스트만 포스팅 할거에여)

- 순차 리스트 : 배열을 기반으로 구현된 리스트

- 연결 리스트 : 메모리의 동적 할당을 기반으로 구현된 리스트

 

References

📚 윤성우의 열혈 자료구조 : C언어를 이용한 자료구조 학습서

📄 https://reakwon.tistory.com/25