[자료구조] 링크드 리스트 (Linked List)
1. 링크드 리스트 (Linked List) 구조
- 연결 리스트라고도 함
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
- 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원
- 링크드 리스트 기본 구조와 용어
- 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
- 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
2. 간단한 링크드 리스트 예
Node 구현 및 노드와 노드를 연결하기
- 보통 파이썬에서 링크드 리스트 구현시, 파이썬 클래스를 활용함
- 파이썬 객체지향 문법 이해 필요 (참고: https://www.fun-coding.org/PL&OOP1-3.html )
링크드 리스트에 노드를 추가하고 데이터를 출력하기
3. 링크드 리스트의 장단점 (전통적인 C언어에서의 배열과 링크드 리스트)
- 장점
- 미리 데이터 공간을 미리 할당하지 않아도 됨
- 배열은 미리 데이터 공간을 할당 해야 함 - 단점
- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
- 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
4. 링크드 리스트의 복잡한 기능1 (링크드 리스트 데이터 사이에 데이터를 추가)
- 링크드 리스트는 유지 관리에 부가적인 구현이 필요함
링크드 리스트 중간에 새로운 노드를 추가하기
(코드를 두 번 실행해서 1.5가 두 번 추가됐다..)
파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기
5. 링크드 리스트의 복잡한 기능2 (특정 노드를 삭제)
이전에 구현한 NodeManagement 클래스에 delete 메서드를 추가한다.
head 노드 삭제 테스트
중간 혹은 마지막 노드 삭제 테스트
6. 다양한 링크드 리스트 구조
- 더블 링크드 리스트(Doubly linked list) 기본 구조
- 이중 연결 리스트라고도 함
- 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
더블 링크드 리스트 구현
더블 링크드 리스트 테스트
7. 프로그래밍 연습
6번에서 만든 NodeMgmt 클래스 안에 함수를 추가하며 연습한다.
연습 1: 노드 데이터가 특정 숫자인 노드를 검색하는 함수를 만들고, 테스트해보기
테스트
연습 2: 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고, 테스트해보기
테스트
insertBefore()에서 while문을 통해 찾은 node는 data가 37인 노드이다.
해당 노드 앞에 data가 65인 노드를 추가하기 위해서는,
old 노드와 new노드를 연결시키고, new 노드와 node 노드를 연결시켜야 한다.
연습 3: 노드 데이터가 특정 숫자인 노드 뒤에 데이터를 추가하는 함수를 만들고, 테스트해보기
테스트
insertAfter()에서 while문을 통해 찾은 node는 data가 65인 노드이다.
해당 노드 뒤에 data가 27인 노드를 추가하기 위해서는,
node 노드와 new 노드를 연결시키고, new 노드와 old 노드를 연결시켜야 한다.
💛 개인 공부 기록용 블로그입니다. 👻