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

Linked List(연결리스트) 란?

1. 무엇이 좋은가?

• 메모리를 미리 할당하지 않아도 됩니다.
• 데이터 추가/삭제가 배열보다는 유리하다.

2. 무엇이 나쁜가?

• 메모리를 할당하지 않아도 되지만 다음 데이터를 가르켜야 하는 포인터의 정보가 들어가야 하므로 공간효율이 좋지 않습니다.
• 인덱스로 검색되지 않습니다. 검색도 느립니다. 보안책으로 더블링크드리스트가 존재.. 하지만 역시 느립니다.
• 구현을 따로해야 해서 귀찮..;;

아래 그림을 보고 이해해 보자

위 그림은 기본적인 연결리스트의 자료 구조입니다. 보시다 시피 포인터의 공간이 필요해요.

인덱스로 찾거나 그런거 없습니다. 

더블링크드 리스트 구조입니다.

만약 Data4의 Next 포인터에 Data1을 가르키게 한다면 순환 링크드리스트가 됩니다. 
자료가 10,000개 있다고 치고 8,000번째 자료를 찾는데 처음부터 찾지 않고 역순으로도 찾을 수 있도록 보완한 것 입니다.

3. 어디서 쓰나요?

• 배열을 만들고 싶어도 이게 대체 몇 개의 데이터가 담길지 도무지 알수 없는 경우
• 추가 / 삽입 / 삭제 등이 빈번하게 이뤄지는 경우

FAT 하드디스크 방식에 대해 아시나요?
파일 삭제 / 추가 / 변경 이 빈번하게 이루어지고 당최 몇개가 담길지 모르는 이런 경우 사용합니다.

4. 시간 복잡도

단순 링크드리스트일 경우, 최악의 경우 O(n)일테고, 더블링크드 리스트면 '아 그래도 조금 빠르겠지? 하하하..' 하면서 O(n/2) 이 나오겠지만, 시간복잡도일 경우 상수를 사용하지 않기때문에 둘다 O(n) 으로 같습니다.

5. 정말 느리기만 한가요?

아니에요. 데이터의 삭제/추가/변경 에도 용이하고 검색도 빠른 데이터 베이스 인덱스 기법중 하나인 B+Tree가 바로 이 연결리스트기법중 하나 입니다. 연결리스트와 Heap을 합쳐놓은 개념입니다. 아래 그림을 보시면 이해가 되실거에요. 위키피디아에서 업어왔습니다.

6. 키포인트

• 검색이 용이하지 않음
• 데이터 추가/삭제가 배열보다 유용함
• 데이터가 들어갈 공간을 미리 지정해 주지 않아도됨
• 포인터 공간으로 인해 공간 효율이 떨어짐

7. 추가 Tip

파이썬을 제외하고는 다른 언어로 구현해 본적은 없습니다.

• 파이썬에서는 리스트 기능을 사용하고
• 연결리스트 클래스를 만들어준 후
• 클래스 메소드에 추가/변경/삭제 등을 구현해주면 됩니다.
• 연결리스트의 가장 첫 데이터와, 더블링크드리스트일경우 마지막 데이터도 시스템은 항상 알고 있어야 합니다.

주피터노트북으로 작정해서 올려둘께요!