TIL #119 : [Data Structure] 연결 리스트 Linked List

셀레스틴 허·2021년 4월 20일
0
post-thumbnail

Linked list

Linked list란?

Array list와는 다르게 엘리먼트와 엘리먼트 간의 연결을 이용해서 리스트를 구현하는 것을 의미한다. 연결 리스트에서는 엘리먼트를 노드 또는 버텍스라고 부른다.

연결 리스트는 데이터와 다음 노드의 주소를 담고 있는 노드들이 한줄로 연결되어 있는 선형적인 데이터 방식의 자료구조다. Linked list의 최대 장접은 바로 데이터를 삽입하고 삭제하기 쉽다는 것이다. 대신, linked list에서 특정 위치의 데이터를 검색하기 위해서 첫 노드부터 탐색을 시작해야 한다. 그 시간이 O(n) 만큼 걸리기 때문에 탐색에 있어서 배열, 또는 트리 구조에 비해 느리다.

노드는 최소한 두 가지 정보를 알고 있어야 한다.

  1. 노드의 값
  2. 다음 노드

노드의 기본 구조를 살펴보면 더욱 이해가 될 것이다.

노드 기본 구조:

  1. 헤드

head는 건물의 출입문과도 같다. linked list를 사용하기 위해서는 head가 가르키는 첫번째 노드는 찾아야 한다. 왜? linked list는 특정 위치의 데이터를 찾을 수 없다. 첫 노드부터 탐색해야 하기 때문이다. 즉 head를 찾는 것이 매우 당연하고 중요하다!

  1. 노드(데이터필드, 링크필드) - 연결됨

데이터필드는 value라는 이름의 변수, 링크필드는 next 변수를 사용한다. value에는 노드값이 저장되고 next에는 다음 노드의 포인터, 또는 참조값을 저장해서 노드와 노드를 연결시킨다.

데이터 추가

시작부분에 추가

  1. 새로운 노드 생성
  2. 새로운 노드의 다음 노드(next)로 첫번째 노드를 가르키게 함
  3. 새롭게 만든 노드가 첫번째 노드가 될 수 있도록 head의 값을 변경

중간부분에 추가

array list와 가장 차이점이 나타나는 부분이다. 배열은 중간 추가, 삭제할 경우 해당 엘리먼트의 뒤에 있는 모든 엘리먼트의 자리를 이동시켜야 했지만, linked list의 경우 추가/삭제가 될 엘리먼트의 이번, 이후 노드의 참조값(next)만 변경하면 되기 때문에 속도가 빠르다.

2번째 자리에 추가하고 싶다고 가정했을 때:
1. head를 참조해서 첫번째 노드를 찾아야 함
2. 첫번째 노드의 다음 노드(두번째)를 변수에 저장함
3. 두번째 노드의 다음 참조값도 변수에 저장함
4. 새로운 노드 생성함
5. 첫번째 노드의 다음 참조값으로 새로운 노드를 할당함
6. 새로운 노드의 다음 참조값으로 두번째 노드를 할당함

그럼 자연스럽게:

첫번째 노드 -> 새로운 노드 -> 두번째 노드

데이터의 제거

데이터를 추가하는 방식과 매우 비슷하다.

3번째 자리를 삭제하고 싶다고 가정할 때:
1. head를 참조해서 첫번째 노드를 찾음
2. 두번째 노드로 이동함
3. 세번째 노드를 찾음
4. 두번째 노드의 다음 참조값(next)를 네번째 노드로 변경함(.next.next)
5. 세번째 노드를 지움(delete)

인덱스로 데이터 조회

linked list의 경우 head가 가르키는 노드부터 시작해 순차적으로 노드를 찾아가야 한다. 그러나 array list는 해당 엘리먼트에 바로 접근할 수 있다.

Linked list의 종류

  • Singly linked list
  • Doubly linked list
  • Circular linked list

Linked list의 장, 단점

장점

  • 데이터 삽입, 삭제 쉬움
  • 삽입과 삭제가 O(1)에 이루어진다
  • linked list 길이 동적으로 조절 가능
  • 🔥🔥🔥 메모리 관리가 용이하다

단점

  • 특정 노드를 바로 접근할 수 없음 (인덱싱을 통한 접근이 오래 걸림)
  • 탐색이 O(N) 걸림 (head to tail)
  • 다음 노드의 위치를 저장하기 위해 추가 공간이 필요함
  • (cache locality를 활용한) 근접 데이터를 사전에 캐시에 저장하기가 어려움
  • linked list를 반대로 탐색하기 어려움

Reference:
https://opentutorials.org/module/1335/8821
https://underflow101.tistory.com/3
https://daimhada.tistory.com/72

profile
Software Developer / 고통은 필연, 괴로움은 선택

0개의 댓글