[코드잇-자료구조1 : 기본 자료구조들] 4. 링크드 리스트

본 게시물은 코드잇의(codeit) 자료구조 시리즈 강의 첫번째 주제인 '기본 자료구조들'을 듣고 정리한 게시물임을 알려드립니다.

- 강의 url : https://www.codeit.kr/topics/data-structure-basics?mediumTypedId=UGxheWxpc3Q6NjZkZDU5YWI4OTg1YTI3ZWRkOTdlOWUz

---

- 저번 챕터에서는 배열과 동적배열에 대해 배웠음. 두 자료 구조의 공통점은 데이터를 순서대로 저장한다는 점이었음.

- 두 자료의 공통점은 데이터를 순서대로 저장한다는 점이었음

- 링크드 리스트도 배열이나 동적배열처럼 데이터를 순서대로 저장해주는 자료구조

1. 링크드 리스트(연결 리스트, Linked List) 개념

링크드 리스트

- 데이터를 순서대로 저장해주는 자료구조

- 동적배열처럼 계속 새로운 요소를 추가할 수 있음

 

단, 동적배열보다 링크드 리스트가 구현 방식이 복잡하며, 상황에 따라 적합한 자료구조가 다름.

링크드 리스트 동작 방식

- 링크드 리스트는 노드라는 단위의 데이터를 저장하고, 데이터가 저장된 각 노드들을 순서대로 연결시켜서 만든 자료구조

예를들어, 박스(노드) 5개가 있다고 가정

 

각 박스에는 이름이 있음 (현승,규리,...)

- 각 박스에는 칸막이가 있으며, 칸막이 왼쪽에는 값을 저장할 수 있고, 오른쪽에는 이름을 저장

 

흩어져있는 박스들을 순서대로 나열하고 싶음. 예를 들어 2,3,5,7,11의 순서대로 나열하고 싶음

- 이를 위해 규리박스 오른쪽에 그 다음의 박스 이름인 태호를 넣고, 다른 박스들도 마찬가지로 지정 가능  

- 현승박스 오른쪽이 비어있으므로 마지막이라는 것을 알 수 있음

- 연결된 박스들의 순서 : 규리 → 태호 → 동욱 → 유나 → 현승

 

이렇게 순서가 있게 연결되어 있어서 '연결 리스트'라고 부름

2. 링크드 리스트 프로그래밍적으로 생각하기

1절에서의 박스 예시를 코드로 구현하는 방식

1절에서의 박스는 '노드'라는 단위

- 각 노드는 하나의 객체로 표현됨

 

각 노드 객체에는 두 가지 속성이 있음 : data, next

- data : 저장하고 싶은 정보

- next : 다음 노드에대한 레퍼런스

 

예를들어, n_1이라는 노드 객체와 n_2라는 노드 객체가 있다고 가정

 

노드 객체가 여러개 있다고 가정

- 각 노드 객체들은 서로 관계가 없고, 메모리에 연속적으로 저장 X

- 그러나, 각 노드들은 다음 노드에 대한 레퍼런스가 있음

head 노드 : 링크드 리스트의 시작점 역할을 하는 첫 번째 노드 객체

- 가장 첫 번째 노드 객체의 메모리 주소만 알고있으면 next를 타고타고가서, 연결되어있는 모든 노드에 접근할 수 있음

 

링크드 리스트의 개념 recap

- head 노드만 있으면 흩어져있는 다른 노드들을 연결지어서 순서 저장 가능

- 배열/동적배열처럼 정보를 원하는 순서로 저장 가능

주의 사항

- 본 강의에서 링크드리스트가 위의 그림처럼 순서대로 나열되어 있어 보여도, 이는 이해를 돕기 위한 것이지,
실제 메모리에서는 여기저기 흩어져 있다.