(22.08.13)자료구조 3 - 연결리스트 1(Linked List 1)

연결리스트(Linked List)란?

• 정의: 추상적 자료형인 List를 구현한 자료구조로서, 노드(Node)를 하나의 Data라고 정의할 때
  Node에 실제로 필요한 value뿐만 아니라, 포인터 변수로 다음 데이터의 주소를 저장해놓는 것이다.
• 장점
  • 추가/삽입/삭제 가 빠르다.
  • 연속된 메모리 공간이 필요하지 않다.
• 단점 : 순차적 탐색만 가능하기 때문에, 탐색의 속도가 느리다.
• 탐색, 정렬을 자주 하면 배열, 추가/삭제가 많으면 연결리스트를 사용한다.

*B+ tree라는 자료구조는  연결리스트 + heap의 모양새로, 데이터의 추가/삭제/정렬/조회 모두에 용이하다.

 

구현 방법

1. 단순 연결 리스트(Singly Linked List)

출처:나무위키

 

 

 

 

 

 

• 다음 노드에 대한 참조만을 가지는 가장 단순한 형태의 연결 리스트다
• 탐색의 시간 복잡도는 O(n)이다.
• 주소(포인터 변수)하나가 잘못되어도 체인이 전부 끊기는 문제가 발생해, 안정적인 자료구조가 아니다.
• 파일 시스템 중 FAT가 이것으로 구현되어 있다.
  그래서 FAT는 자료 유실 가능성이 높고, 랜덤 액세스 성능도 낮다.

struct NODE{
    struct NODE* next;
    int data;
};

위와 같이 단순한 구조로 되어있다.

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

 

 

 

 

 

 

• 이전 뿐만아니라, 다음 노드의 참조(주소)도 가지고 있다면 이중 연결리스트가 된다. -> 뒤로의 탐색이 단순보다 상대적으로 빠르다.
• 단순 연결리스트는 삭제가 O(n)이지만, 이중 연결리스트에서는 훨씬 간단하다.
• 대신 관리할 참조가 두 개이기 때문에 삽입, 정렬의 연산이 늘어나고 차지하는 메모리도 늘어난다.
• 단순 연결리스트에 비해 손상에 강한편이다.
  • Head와 Tail Node를 갖고 있다면 둘중 하나만으로도 리스트 전체가 순회가 가능하기 때문이다.
  • 그러나 보정 알고리즘을 구현하지 않으면 역시 손상에 취약하다.

struct NODE{
    struct NODE* next;
    struct NODE* prev;
    int data;
};

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

 

 

 

 

 

 

• Tail의 참조가 다시 Head를 가리키는 것이다.
• 이중 연결리스트의 처음과 끝을 이으면 이중 원형 연결 리스트를 구현할 수 있다.

 

시간 복잡도

(출처: https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/)

ArrayList와의 비교

 

 

 

참고 출처:https://namu.wiki/w/%EC%97%B0%EA%B2%B0%20%EB%A6%AC%EC%8A%A4%ED%8A%B8

https://woovictory.github.io/2018/12/27/DataStructure-Diff-of-Array-LinkedList/