[자료구조] 연결 리스트 (linked list)

• 배열 : 동일한 타입의 변수가 연속된 공간에 존재하는 자료구조
• 연결 리스트 : 서로 다른 위치에 존재하는 데이터를 포인터를 이용해 연결한 자료구조

---

연결리스트 정의

---

 

 

자료구조는 탐색/삽입/삭제 모두 빠르게 수행될 수 있도록 개발되어져 왔다.

배열과 연결리스트는 모두 선형 자료구조에 속한다. (순서가 존재한다는 의미이다)

 

하지만 배열은 동일한 타입의 변수가 연속된 메모리에 저장되는 자료구조인 반면,

연결리스트(linked list)는 node로 구성되어 있고, 각 node는 pointer로 연결되어 있다.

여기서 pointer로 연결되어 있다는 것이 매우 중요한데, 이 의미는 node들이 아무 곳이나 존재할 수 있다는 의미이다.

 

노드는 데이터와 포인터로 구성되어 있다.

• 데이터 : 데이터를 저장하기 위한 공간
• 포인터 : 주소를 저장하는 변수 (singly linked list에서는 다음 node의 주소를 저장하고 있다)
  • 다음 노드의 "주소"를 저장하기 때문에 배열과 달리 노드가 연속된 공간에 존재할 필요가 없다.
  • 하지만 다음 node의 주소만을 저장하고 있기 때문에 "순차접근"만 가능하다

 

• 배열:
  • 탐색 : O(1) - index를 통해 접근이 가능하므로 (임의 접근 가능)
  • 삽입 : O(n)
  • 삭제 : O(n)
• 연결리스트:
  • sorted
    • 탐색 : O(n) (비정렬되어 있는 것에 비해 평균적으로 2배 빠르다)
    • 삽입 : Search(O(n)) + O(1)
    • 삭제 : search(O(n)) + O(1)
  • unsorted 
    • 탐색 : O(n)
    • 삽입 : Search(O(n)) + O(1) or O(1)
    • 삭제 : search(O(n)) + O(1)

 

 

---

연결리스트 삽입, 삭제, 조회

---

 

 

 

연결 리스트에서의 삽입 (출처 : geeksforgeeks)

linked list를 구현할 때 일반적으로 삽입, 삭제, 조회가 가능하도록 코드를 작성해야 한다.

 

• 1. 삽입
  • 첫 번째 위치에 삽입하고자 하는 경우
    • 삽입하고자 하는 노드 생성
    • 삽입하고자 하는 노드의 다음 노드가 이전의 head가 되도록
  • 마지막 위치에 삽입하고자 하는 경우
    • 삽입하고자 하는 노드 생성
    • 이전 tail노드가 자신을 가리키도록 설정
  • 처음도 마지막도 아닌, 중간에 삽입하고자 하는 경우
    • 삽입하고자 하는 노드(E) 생성
    • 삽입하고자 하는 이전 위치의 노드(B)가 가리키는 노드(C)를 E도 가리키도록 설정
    • 삽입하고자 하는 이전 위치의 노드(B)가 나(E)를 가리키도록 설정
    • 삽입 끝!
• 2. 삭제
  • 만약 linked list에서 삭제를 한다면, (위의 예시에서 B-C-D 노드가 연결되어 있고, C를 삭제한다고 가정)
  • 처음 노드를 삭제하고자 하는 경우
    • 첫 번째 노드 따로 변수에 저장 
    • head가 두 번째 노드를 가리키도록 하면 된다
    • 첫 번째 노드 메모리 해제
  • 마지막 노드를 삭제하고자 하는 경우
    • 마지막 노드 따로 변수에 저장 
    • 마지막 이전 노드가 NULL이 되도록 하면 된다
    • 마지막 노드 메모리 해제
  • 처음도 아닌, 마지막도 아닌 중간 노드 삭제하고자 하는 경우
    • (B - C - D 에서 C 노드를 삭제하고자 하는 경우)
    • B의 next 노드(C)를 따로 저장
    • B의 next가 D 노드가 되도록 설정
    • C 노드의 메모리 해제
• 3. 조회
  • 1) linked list가 value 순서대로 정렬이 되어있는 경우
    • 노드를 순차적으로 접근하며 내가 찾고자 하는 값과 비교하는데, 만약 어떤 node의 value가 내가 찾고자 하는 값보다 크다면 search 실패한 것이다.
    • 이렇게 정렬이 되어있는 경우, 중간에 끊을 수 있다.
  • 2) linked list가 value 순서대로 정렬이 되어있지 않은 경우
    • 처음부터 끝까지 노드를 순차적으로 접근해가며 찾고자 하는 value를 탐색해야 하낟.
    • 정렬이 되어있지 않은 경우, 중간에 끊을 수 없다.

 

 

---

linked list 응용

---

 

• duumy node
  • head와 tail 사용하여 예외처리를 보다 쉽게 할 수 있다.
• circular list
  • 마지막의 노드가 첫 노드를 다시 가리키는 구조
• doubly linked list
  • 양방향의 link가 존재
    • 내 앞의 노드의 주소
    • 내 뒤의 노드의 주소
• linked list의 사용
  • linked list의 search 성능은 좋지 않으므로 search가 거의 없고,
    데이터를 순서대로 읽은 작업을 수행하는 경우에 linked list가 사용된다고 한다.
  • +) 배열과 같은 경우 삽입/삭제 성능이 좋지 않으므로
    데이터가 잘 바뀌지 않고, 탐색이 자주 일어나는 경우에 사용된다
    • 예를 들어 사전과 같은 데이터

 

---

#13. 팰린드롬 연결리스트

<fast runner, slow runner>

linked list의 경우 순차접근만 가능하기 때문에 따로 길이를 저장하지 않으면, 어디가 중간인 지 알 수 없다.

따라서 fast runner, slow runner 개념을 도입하였다.

 

slow runner는 1 step씩, fast runner는 2 step씩 이동하기 때문에 fast runner가 linked list의 끝 지점에 도달한 경우 slow runner는 중간 지점에 도달한다. 따라서 linked list의 중간 지점에 도달한 순간을 알 수 있게 되는 것이다.

 

 

#14. 두 정렬 리스트의 병합

재귀나 다른 코드에서 return할 때 return x or y, return x and y 과 같은 표현을 사용하는 것을 보고

이것이 의미하는 바에 대해 알아보았다.

return x or y : x가 false이면 y를 그렇지 않으면 x를 return

• x가 false -> false or y = y -> 따라서 y를 return
• x가 true -> true or y = true -> 따라서 x를 return

return x and y : x가 false이면 x를 그렇지 않으면 y를 return

• x가 false -> false and y = false -> 따라서 x를 return
• x가 true -> true and y = y -> 따라서 y를 return

(참고 : stackoverflow.com/questions/4477850/and-or-operators-return-value)