주니어 백엔드 개발자 인터뷰

# 연결 리스트 (Linked List)

# 연결 리스트란 무엇인가요?

  • 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조입니다.
  • Node로 연결한 구조이며, 각 Node들은 데이터와 다음 Node에 대한 참조(주소)값을 가지고 있습니다.
    연결리스트
  • Collection 프레임워크의 일부이며 java.util 패키지에 LinkedList로 소속되어 있습니다.

# 연결 리스트 종류

  • 싱글 연결 리스트 : next 포인터만 가집니다.
  • 이중 연결 리스트 : next 포인터와 prev 포인터를 가집니다.
  • 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리킵니다.

참고로, java util패키지의 LinkedList는 이중 연결 리스트와 같은 형식으로 구성되어있습니다.

# 연결 리스트 사용법

  • LinkedList 선언
LinkedList list = new LinkedList();     //타입 미설정
LinkedList<Integer> num = new LinkedList<>();   //int타입만 집어넣을 수 있음
  • LinkedList 값 추가
list.add(3);    // 3이라는 데이터 추가 (맨 뒤에 추가됨)
list.add(2, 5); // index 2에 데이터 5 추가 
list.addFirst(1);   // 맨 앞 노드에 데이터 추가
list.addLast(2);    // 맨 뒤 노드에 데이터 추가
  • LinkedList 값 삭제
list.remove();    // 맨 뒤에 있는 노드 제거
list.remove(1); // index 1 제거 
list.removeFirst();   // 맨 앞 노드 삭제
list.removeLast();    // 맨 뒤 노드 삭제
list.clear();   //모든 노드 삭제
  • LinkedList 데이터 변경
list.set(2, 10);    // 2번 index에 있는 값을 10으로 변경
  • LinkedList 크기 구하기
list.size();    // 리스트의 크기 구하기
  • LinkedList 값 검색
list.contains(1);    // 리스트에 1이 존재하면 true 반환, 없으면 false 
list.indexOf(1);    // 1이 있는 index 반환, 없으면 -1
  • LinkedList 값 출력하기
list.get(i);    // i번 index에 있는 데이터 출력
list.getFirst();    // 맨 앞에 있는 데이터 출력
list.getLast();     // 맨 뒤에 있는 데이터 출력

for(Integer i : list) { // 향상된 for문을 통한 전체출력
    System.out.println(i);
}

Iterator<Integer> iter = list.iterator();   // Iterator 선언 
while(iter.hasNext()){//다음값이 있는지 체크
    System.out.println(iter.next()); //값 출력
}

# 연결 리스트의 시간 복잡도는 얼마나 되나요?

삽입과 삭제에는 O(1), 탐색에는 O(n)이 걸립니다.

# 연결 리스트를 사용하는 이유는 무엇인가요?

  • 리스트의 길이가 가변적이기 때문에 메모리 효율성이 좋습니다.(새로운 요소가 추가될 때, 런타임에 메모리를 할당한다.(동적메모리 할당))
  • 데이터의 추가, 삭제가 편리합니다.

따라서 새로운 데이터를 추가하거나 삭제해야하는 작업이 빈번히 일어날 때 사용하기 좋습니다.

# 연결 리스트의 단점은 무엇이 있나요?

어떤 노드를 search 하거나 데이터를 변경할 때 바로 찾아낼 수 없습니다.
최악의 경우에는 모든 노드를 방문하고 맨 마지막에 있는 노드를 얻는 행위를 반복할 수도 있습니다. (시간 복잡도 : O(n))

# 참고자료

출처: 주홍철.면접을 위한 CS 전공지식 노트.서울:길벗,2022.
출처: https://coding-factory.tistory.com/552

← 벡터(Vector) →