링크드 리스트 (Linked List)

이미지출처: https://beginnersbook.com/2013/12/java-arraylist/

Linked List

• 컴퓨터의 자료를 저장하는 구조의 한 종류
• 일렬로 연결된 데이터를 저장할 때 사용.
• 어떤 데이터가 있다면, 그 데이터는 다음 데이터의 주소를 가지고 있는 구조

Linked List VS Array

• 배열은 물리적으로 한 곳에 데이터가 몰려있음.
• 그래서 길이를 늘리거나 줄일 수 없음.
• 그에 반해서 Linked List는 중간에 데이터를 삽입 가능
• 앞의 노드가 가지고 있던 주소를 자기가 가지고, 앞의 노드에게는 새로운 데이터의 주소를 넣는다 (붙인다?), (주소가 가리킨다)
• 링크를 뺼때는 앞 뒤의 데이터의 주소를 그에 따라서 바꾸면 된다.
• 하지만 데이터는 그대로 남아있다. (자바에서는 처리해주지만 C나 C++에서는 반드시 안쓰겠다고 명시해야함)
• 배열보다 느리다.

참고

노드(Node)란?: 어떤 데이터 덩어리
잘 와닿는 예시: 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상명세 자료를 노드로 만들고, 1번 학생의 신상명세 자료에 2번 학생 신상명세가 어디있는지 표시를 해 놓는 방식이다. 쉽게 생각하면 자료를 비엔나 소시지마냥 줄줄이 엮어놓은 것이다.
출처: https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

여기서 나오는 질문?

Q: ArrayList VS LinkedList ?
A: 삽입 및 제거 작업은 ArrayList에 비해 LinkedList에서 좋은 성능을 제공합니다. 따라서 응용 프로그램에서 빈번한 추가 및 삭제가 필요한 경우 LinkedList가 최선의 선택입니다.
검색(get method) 작업은 Arraylist에서는 빠르지 만 LinkedList에서는 빠르지 않으므로 추가 및 제거 작업이 적고 검색 작업 요구 사항이 더 많은 경우 ArrayList가 최선의 방법입니다.
이유&출처: https://beginnersbook.com/2013/12/difference-between-arraylist-and-linkedlist-in-java/

Linked List 개념 (유튜브)