[Linked Lists]2. 단일 연결 리스트 - 2

목차

1. node의 구성

2. 특별한 node

3. Head에서의 삽입

4. Head에서의 삭제

5. Tail에서의 삽입

6. Tail에서의 삭제

 

1. node의 구성

 앞선 게시물에서도 언급하였듯이, node class는 그 node가 지닌 data와, Singly Linked List의 경우 다음 node의 주소값을 지니고 있습니다. 이를 python으로 표현해보면,

class Node:
    def __init__(self, data: int):
        self.data = data
        self.next = None

 이렇게 나타낼 수 있습니다.

 

2. 특별한 node

 Linked List는 크게 2가지 특별한 node가 있다고 할 수 있습니다.

<Head와 Tail>

1. Head

- 맨 앞 node으로서, LInked List는 시작 node인 Head의 주소를 가지고 있는다.

 

2. Tail

- 맨 뒤의 node으로서, node안의 next에는 주소가 없는 NULL 상태이다.

 

3. Head에서의 삽입

 LInked LIst에 자료를 추가하고 제거하려면 Head에서 추가/제거하거나 Tail에서 추가/제거하면 됩니다. 이 4가지 과정중 먼저 Head에서 삽입하는 방법에 대해 설명하겠습니다.

 

<Inserting at the Head>

1. 새로운 node를 생성한다

2. 새로운 element 값을 받는다.

3. LInked List에 저장되어 있던 Head의 주소를 새로만든 node의 next에 준다.

4. Linked List에 저장되어 있는 Head의 주소를 새로운 node의 주소로 바꾼다.

 

Head에서 삽입의 특징은 후에 서술할 방법이지만, 속도가 O(1)으로 몹시 빠르다는 점이다.

 

4. Head에서의 삭제

<Removing at the Head>

1. 기존 head의 주소 tmp에 저장(이 node를 지우기 위함)

2. LInked List의 head node 주소를 기존 node의 next node 주소값을 받는다.

3. tmp에 저장되어있는 node를 삭제한다.

 

이 과정도 시간 복잡도가 O(1)으로 짧습니다.

 

5. Tail에서의 삽입

6.<Inserting at the Tail>

1. 새로운 node를 생성한다.

2. 새로운 element 값을 받는다.

3. 새로운 node의 next에 NULL을 대입한다.

4. 기존 Tail의 next에 새로운 node의 주소 값을 대입한다.

5. Linked LIst의 Tail 주소에 새로운 node의 주소를 대입한다.

 

이 과정도 O(1)으로 시간이 짧다.

 

6. Tail에서의 삭제

<Removing at the Tail>

 Singly LInked LIst에서 Tail에서의 삭제를 시행하는 것은 효율적이지 않은 일입니다. 그 이유는 Tail node에서는 이전의 node의 주소 값을 모르기 때문에, 삭제를 하고 싶어도 Tail에 뒤에서 두 번째 node의 주소값을 할당할 수 없기 때문입니다. 그럼에도 Tail에서 삭제를 하려면,

1. Head node에서 시작한다.

2. node에서 next의 주소값이 Tail node일때 까지 이동함

3. next가 Tail node라면 그 node를 Tail로 지정, 그후 tmp에 저장해둔 기존의 Tail node를 삭제

 

이는 Head node에서 Tail 바로 전 node까지 일일히 확인하고 넘어가야 하므로, 비효율적이라고 할 수 있습니다.

 

총 2개의 게시물을 통하여 Singly Linked LIst의 개념에 대해 알아보았으며, 다음 게시물에서는 Singly Linked List를 구현해보도록 하겠습니다.