[JAVA] LinkedList 알꺼같으면서도 모르겠다.

면접에서 가장 자주 나오는 개념인 LinkedList인데... 아는거 같으면서도 잘 모르겠는 부분이 많아서 질문 받아서 대답하면 어버버버 한다... 오늘 해결해보자!

---

https://www.geeksforgeeks.org/introduction-to-linked-list-data-structure

오늘의 한줄 요약: LinkedList 에서 데이터를 찾는 방법은 순차 탐색(Sequential Search)을 기반으로 이루어진다!

LinkedList의 구조 이해

LinkedList는 노드(Node)들의 연결로 이루어져있다.

각 노드는 두가지 요소를 가지고 있음!

• 데이터(Data): 노드가 저장하고 있는 실제 값.
• 포인터(Next): 다음 노드를 가리키는 참조

데이터를 10 -> 20 -> 30 순서로 저장한 LinkedList는 아래와 같다아:

[10 | Next] -> [20 | Next] -> [30 | Null]

• Head: List의 시작 노드를 가리키는 포인터
• Tail: 리스트의 끝 노드, Next가 Null인 노드

LinkedList에서 데이터를 찾는 순서

데이터를 찾는 과정은 처음 노드부터 시작하여 찾을 값이 나올 때까지 하나씩 확인하는 방식이다.

1. Head에서 시작:
   • 탐색은 항상 Head 노드에서 시작한다.
2. 값 비교
   • 현재 노드의 데이터를 찾는 값과 비교한다.
   • 찾는 값과 같으면 탐색을 종료한다.
   • 다르면 다음 노드로 이동한다.
3. 다음 노드로 이동
   • 현재 노드의 Next 포인터를 따라 다음 노드로 이동한다.
4. 반복
   • 위 과정을 리스트의 끝까지(Next가 Null인 노드) 반복한다.
5. 결과
   • 찾는 값이 있다면 해당 노드를 반환하거나 위치를 반환한다.
   • 찾는 값이 없다면 탐색 결과가 Null또는 찾을 수 없음 으로 반환한다.

LinkedList 탐색 과정의 예

자! 이제 예시를 들어보자!

문제: LinkedList에서 값 20을 찾는 과정.

1. Head 노드에서 시작
   • 현재 노드는 [10 | Next].
   • 10과 20을 비교: 다르므로 다음 노드로 이동
2. 다음 노드 확인
   1. 현재 노드는 [20 | Next]
   2. 20과 20을 비교: 같으므로 값 발견! 탐색을 종료한다!
3. 탐색 실패시 (예를 들어 값 40을 찾는 경우)
   
   • 모든 노드를 탐색하지만 값이 발견되지 않음
   • 탐색 종료 후 "값이 없다"는 결과를 반환.

LinkedList에서 탐색의 시간 복잡도

탐색은 순차적(Sequential) 으로 이루어지기 때문에 시간 복잡도는 O(n)이다.

• 최악의 경우: 찾는 값이 리스트의 끝에 있거나, 리스트에 없는 경우.
• 최선의 경우: 찾는 값이 Head에 있는 경우.

LinkedList 탐색 관련 주의점

• 랜덤 엑세스가 불가능
  • LinkedList는 ArrayList와 달리 인덱스를 바로 참조할 수 없다.
  • 항상 처음부터 순차적으로 접근해야 한다.
• 탐색 속도가 느림
  • 데이터가 많아질수록 탐색 속도가 선형적으로 느려진다.
  • 대량의 데이터에 대한 빈번한 탐색이 필요한 경우, ArrayList가 더 효율적이다.
• 복잡한 탐색 구현 시 주의
  • 단순 값 비교 외에 특정 조건에 따라 노드를 탐색하려면 별도의 조건식을 작성해야 한다.

LinkedList에서 값을 삭제하는 방법

20을 삭제해보자!
값을 삭제하려면 20을 포함한 노드의 이전 노드와 다음 노드의 연결을 변경해야 한다.

• 탐색 과정에서 값을 찾음
  • 값이 20인 노드(삭제 대상)를 찾음.
  • 이 노드를 삭제하기 위해 이전 노드와 다음 노드를 연결해야 함.
• 이전 노드의 Next를 변경
  • 이전 노드의 Next(20)를 삭제 대상의 Next로 변경 (삭제된 20의 Next는 25 이므로 25로 변경됨)
  • 예를 들어
    • 삭제 전 15 -> 20 -> 25
    • 삭제 후: 15 -> 25
• 예외처리
  • 삭제 대상이 첫 번째 노드인 경우, 헤드 포인터를 다음 노드로 변경
  • 값이 존재하지 않으면 아무 작업도 하지 않음

 

그렇군! LinkedList 잘 알아봤따! 이제 확실히 알겠군! 이라고 했는데 또 돌아서면 까먹음

 

** 그냥 하루하루 개인 공부한 것을 끄적 거리는 공간입니다.

이곳 저곳에서 구글링한 것과 강의 들은 내용이 정리가 되었습니다.

그림들은 그림밑에 출처표시를 해놓았습니다.

문제가 될시 말씀해주시면 해당 부분은 삭제 하도록하겠습니다. **