[자료구조] 단방향 연결 리스트 (Singly Linked Lists)

 

 Singly Linked Lists 

 

---

 

단방항 연결 리스트란?

• 배열처럼 순서에 따라 다수의 데이터를 저장하는 자료구조
• 시작점인 head와 마지막 점인 tail로 구성됨
• 다수의 node로 구성되고, 각 node에 value를 저장
• 각 node들은 next 포인터로 연결되어 있음
• 각 node들은 다음 node들을 가리키는 정보를 가지고 있어야 하고, 다음 노드가 없을 경우 null을 반환 

 

 

 

next pointer로 연결되어 있고, 다음 노드가 없을 경우 null 반환

 

 

 

배열(Array)과의 차이

 

Search (접근)

• 배열은 데이터들에 Index가 부여되서 Index만 찾으면 쉽게 접근 가능하지만, 단방향 연결리스트는 첫번째 노드부터 순서대로 나아가 값을 찾아야 한다. (Random Access 불가능)
• 배열은 엘레베이터가 있는 빌딩과도 같아서 5층을 누르면 5층으로 갈 수 있지만, 단방향 연결리스트는 엘레베이터가없는 빌딩과도 같아서 5층으로 가려면 1층부터 걸어 올라가야 한다.

 

 

 

출처 : Colt Steele

 

 

삽입(Insertion) & 삭제 (Deletion)

• 하지만 Index가 없기 때문에, 단방향 리스트는 삽입/삭제가 용이하다.
• 배열의 경우 삽입/삭제 시 인덱스도 마찬가지로 수정되어야 하지만, 리스트는 그럴 필요가 없기 때문이다.

 

 

 

결론

단방향 연결 리스트의 경우, 접근은 어렵지만 삽입/삭제는 용이하기 때문에 적은 양의 데이터를 처리하거나 리스트에 저장만 하면 될 경우 사용하는 것이 좋다.

 

 

 

Reference

Colt Steele, JavaScript 알고리즘 & 자료구조 마스터클래스