LinkedList

연결리스트란?

연결리스트는 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다.

 

선형, 비선형 자료구조

• 선형 자료구조 : 배열, 연결리스트 👉 면접에서 둘의 차이를 설명하는 문제가 자주 나옴
• 비선형 자료구조 : 트리, 그래프, 해쉬

 

배열 vs 연결리스트

k 번째 원소 조회, 변경

• 배열 : O(1)
• 연결리스트 : O(k) 👉 배열과 다르게 공간에 원소들이 연속해서 위치하므로

 

임의의 위치에 원소를 추가, 제거

• 배열 : O(N) 👉 중간 삽입 시 그 뒤의 원소들을 전부 한 칸씩 밀어야하므로
• 연결리스트 : O(1)

 

마지막 위치에 원소 추가, 제거

• 배열 : O(1)
• 연결리스트 : O(1)

 

메모리 상의 배치

• 배열 : 연속
• 연결리스트 : 불연속

 

추가적으로 필요한 공간 (Overhead)

• 배열 : 없음
• 연결리스트 : O(N) 👉 이전과 다음원소의 주소 값을 가지므로 (32비트 컴퓨터라면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요, 64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위이니 8N 바이트가 추가로 필요. 즉 N에 비례하는 메모리를 씀)

 

연결리스트 종류

단일 연결 리스트 (Singly Linked List)

• 각 원소가 자신의 다음 원소의 주소를 들고 있다.

 

이중 연결 리스트 (Doubly Linked List)

• 각 원소가 자신의 이전 원소와 다음 원소의 주소를 들고 있다.
• 원소가 가지고 있어야 하는 정보가 1개 더 추가되니 메모리를 더 사용한다는 단점이 있다.

 

원형 연결 리스트 (Circular Linked List)

• 처음과 끝이 연결되어 있다.
• 그림은 단일 연결 리스트로 표시했지만, 각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 된다.

 

이중 원형 연결 리스트 (Doubly Circular Linked List)

이중 연결 리스트 + 원형 연결 리스트 로 결합된 형태.

 

ArrayList VS LinkedList

• 마지막 위치에서 추가, 삭제

  • ArrayList : O(1)
  • LinkedList : O(1)
  • 단, ArrayList의 크기가 충분하지 않으면, 새로운 크기를 생성하고 데이터를 복사하는 일이 발생하므로 LinkedList보다 느릴 수 있다.

• 중간에 데이터 추가, 삭제

  • ArrayList : O(N) 👉 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야 하므로 처리속도가 느리다.
  • LinkedList : O(1) 👉 LinkedList는 각 요소 간의 연결만 변경하면 되므로 처리속도가 빠르다.

• index 조회

  • ArrayList : O(1)
  • LinkedList : O(N)
  • LinkedList는 데이터의 개수가 많아질수록 접근시간 (데이터를 읽어오는 시간, access time) 이 길어진다는 단점이 있다.

• value 조회

  • ArrayList : O(N)
  • LinkedList : O(N)

   

참고

• https://blog.encrypted.gg/932?category=773649
• https://pridiot.tistory.com/66
• https://devlog-wjdrbs96.tistory.com/64
• https://blog.naver.com/diddnjs02/221957843414