3. 연결 리스트(Linked List)

1. 연결 리스트 구조와 특징

동적인 선형 자료 구조로서, 데이터 요소들이 노드(Node)라는 단위로 저장되고 서로 연결되어 있다. 

1-1. 연결 리스트의 구조

 - 노드(Node) :

 * 각 노드는 두 부분으로 구성되는데 하나는 데이터를 저장하는 부분(data), 다른 하나는 다음 노드를 가리키는 부분(next)

 * 마지막 노드의 next는 None을 가리켜 연결리스트의 끝을 나타낸다.

 

- Head:

 * 연결 리스트의 첫 번째 노드를 가리키는 참조이다.

 * 리스트에 접근하거나 순회할 때 시작점으로 사용된다.

 

 

1-2. 연결 리스트의 특징

1. 동적크기(Dynamic Size):

 * 연결 리스트는 미리 크기를 정할 필요 없이, 필요에 따라 동적으로 크기가 조정된다.

2. 비연속 메모리 할당(Non-Contiguous Memory Allocation)

 * 배열과 달리, 연결 리스트의 노드들은 메모리 상에서 연속적으로 위치하지 않아도 된다. 각 노드는 다음 노드의 주소 정보를 가지고 있어 연결된다.

3. 삽입과 삭제의 용이성(Ease of Insertion and Deletion)

 * 새로운 요소를 삽입하거나 기존 요소를 삭제하는 과정이 배열에 비해 간단하다. 이는 연결 리스트에서는 재배열이 필요 없기 때문이다.

4. 메모리 효율(Memorry Efficiency)

 * 사용되는 메모리는 리스트의 실제 크기에 따라 달라진다. 고정된 크기의 배열과 대비된다.

5. 자료 구조 구현의 응용

 * 스택(stack), 큐(Queue) 등의 다양한 추상 자료형(ADT) 구현에 사용된다.

 

1-3. 단일 연결 리스트(Singly Linked List)

가장 기본적인 연결 리스트 유형으로, 각 노드가 오직 다음 노드로 링크만을 가지고 있는 구조이다. 

리스트는 순차적으로만 순회할 수 있으며 주로 간단한 애플리케이션에 사용된다.

연결 리스트를 생성 하고 각 노드를 순회하며 데이터를 출력 한다.

 

1-4. 연결 리스트의 출력

 기본적인 작업으로, 연결리스트의 순회 및 노드 추가 방법은 구조를 이해하고 활용하는데 중요한 요소이다.

 

1. 연결 리스트의 데이터 출력

연결 리스트를 순회하면서 각 노드의 데이터를 출력하는 과정은 비교적 간단하다.

• 이를 위해 별도의 변수(예: node)를 사용하여 head부터 시작하여 리스트를 순회한다.
• 각 노드에서 data 값을 출력하고, next를 통해 다음 노드로 이동한다.
• node가 None이 될 때까지 이 과정을 반복한다.

 

2. 연결 리스트의 끝에 노드 추가

• 새 노드를 리스트의 끝에 추가하려면, 먼저 마지막 노드를 찾아야 한다.
• 마지막 노드는 next가 None인 노드다.
• 마지막 노드를 찾은 후, 해당 노드의 next를 새 노드로 설정한다.

 

3. 연결 리스트의 시작에 노드 추가

• 연결 리스트의 시작 부분에 새 노드를 추가하는 것은 마지막에 추가하는 것보다 간단하다.
• 새 노드를 생성하고, 이 노드의 next를 현재 head로 설정한다.
• 그런 다음, head를 새 노드로 업데이트한다.

2. 연결 리스트 활용

2-1. 연결 리스트 생성

객체 지향 프로그래밍 개념을 활용하여 효율적으로 자료 구조를 관리하는데 좋은 예시이다. 

1. Node 클래스 정의

연결리스트의 각 요소를 나타내는 Node 클래스를 정의한다.

클래스는 data와 next 두 개의 속성을 가진다.

2.LinkedList 클래스 정의

LinkedList 클래스는 연결 리스트를 나타낸다.

여러 메서드를 포함하여 리스트를 조작할 수 있다.

3. 메서드 구현

• appendleft(x): 연결 리스트의 처음에 x를 추가한다.
• append(x): 연결 리스트의 끝 x를 추가한다.
• popleft(): 연결 리스트에서 첫 노드의 값을 반환하고, 노드는 삭제한다.
• pop(): 연결 리스트에서 마지막 노드의 값을 반환하고, 노드는 삭제한다.
• insert(i, x): 연결 리스트의 i번 인덱스에 x를 추가한다.
• remove(x): 연결 리스트에서 값이 x인 노드를 찾아 삭제한다.
• reverse(): 연결 리스트를 제자리에서 순서를 뒤집는다.

4. 특수 메서드 구현

• __len__ : len() 함수를 사용할 때 연결 리스트의 길이를 반환한다.
• __contains__ : 연산자 in과 not in을 사용할 때 연결 리스트 내의 값을 검사하여 True, False를 반환한다.
• __str__ : str()과 print() 함수를 사용할 때 출력할 문자열을 반환한다.