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

이해를 위해 정리하고 있긴 하지만 틀린부분이 있으면 알려주심 수정하겠습니다. 

 

연결리스트

• 각 노드가 한줄로 연결되어 있는 자료 구조
• 각 노드는(데이터, 포인터) 형태를 가짐
  • 포인터 = 다음 노드의 메모리 주소를 가리키는 목적으로 사용
  • 연결성 = 각 노드의 포인터는 다음 혹은 이전 노드를 가리킴

연결 리스트를 이용하면 다양한 자료구조를 구현할 수 있음(스택, 큐)

• 파이썬은 연결리스트를 활용한 자료구조 제공함
• 동작 방식을 알고 있으면 다양하게 활용 가능함

연결리스트 와 배열의 장단점

 

특정 위치의 데이터 삭제 시, 일반적인 배열에서는 O(N) 만큼의 시간 소요됨

연결 리스트의 경우 연결만 끊어주면됨

따라서 삭제할 위치를 정확히 알고 있는 경우 O(1)의 시간이 소요

 

 

복잡도

 

어레이 삽입

새로운 원소를 특정 위치에 넣으면 데이터를 넣기 위해 넣을 자리부터 한칸씩 오른쪽으로 데이터를 밀어서 넣을 자리에 빈 공간을 만들어줘야함

 

어레이 삭제

원소를 제거 한뒤 오른쪽에 있는 원소를 한칸씩 왼쪽으로 당겨줌

 

연결 리스트 에서의 삽입, 삭제

 

Insert(삽입): 삽입할 위치를 알고 있다면, 물리적인 위치를 한 칸씩 옮기지 않아도 삽입할 수 있음

 

삽입하는 인덱스의 위치에 원소가 들어간다고 하면, 그 전의 노드에서 포인터로 새원소를 가리키도록 만들어주고

 

새로 들어간 원소가 그다음 노드를 포인터로 가리키도록 만들면됨

 

Remove(삭제): 삭제할 위치를 알고 있다면, 물리적인 위치를 옮기지 않아도됨

 

삭제할 노드를 건너뛰고 다음 노드를 바로 가리키로도록 포인터를 연결해주면됨

 

붙이기(Append) 

 

뒤에 붙일 때는 마지막 노드의 다음 위치에 원소를 넣으면 됨

 

연결 리스트(Linked List)에서는 배열(Array)과 달리 크기의 제약  없이 새로운 원소 추가 가능

- 배열은 미리 만들어 놓은 크기만큼 데이터를 넣어 사용이 가능

- 연결 리스트에서는 남는 공간에 새로운 데이터를 할당한 뒤에 포인터만 연결해주면 됨

 

 Node 클래스 = data와 next 를 가지고 있음

data = 실제로 담으려는 데이터

next = 다음 노드 위치 (None 으로 한 이유는 다음 위치가 처음에는 비어 있기 때문에)

 

 

전체 코드

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


class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        if self.head == None:
            self.head = Node(data)
            return
        # 마지막 위치에 노드 추가
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    # 모든 노드를 하나씩 출력
    def show(self):
        cur = self.head
        while cur is not None:
            print(cur.data, end=" ")
            cur = cur.next

    # 특정 인덱스(index)의 노드 찾기
    def search(self, index):
        node = self.head
        for _ in range(index):
            node = node.next
        return node

    # 특정 인덱스(index)에 노드 삽입
    def insert(self, index, data):
        new = Node(data)
        # 첫 위치에 추가하는 경우
        if index == 0:
            new.next = self.head
            self.head = new
            return
        # 삽입할 위치의 앞 노드
        node = self.search(index - 1)
        next = node.next
        node.next = new
        new.next = next

    # 특정 인덱스(index)의 노드 삭제
    def remove(self, index):
        # 첫 위치를 삭제하는 경우
        if index == 0:
            self.head = self.head.next
            return
        # 삭제할 위치의 앞 노드
        front = self.search(index - 1)
        front.next = front.next.next

linked_list = LinkedList()
data_list = [1, 2, 3, 4, 5, 6, 7, 8]

for data in data_list:
    linked_list.append(data)

 

결과

print('data:', end=' ')
linked_list.show()

linked_list.insert(4, 4)
print("\ndata:", end=" ")
linked_list.show()

linked_list.insert(0,0)
print("\ndata:", end=" ")
linked_list.show()

linked_list.remove(7)
print("\ndata:", end=" ")
linked_list.show()

linked_list.remove(0)
print("\ndata:", end=" ")
linked_list.show()

linked_list.insert(7, 2)
print("\ndata:", end=" ")
linked_list.show()

 

이렇게 나옴

data: 1 2 3 4 5 6 7 8   - 노드 전체
data: 1 2 3 4 4 5 6 7 8  - 인덱스(4) 위치에 4 추가
data: 0 1 2 3 4 4 5 6 7 8  - 인덱스(0) 위치에 0 추가
data: 0 1 2 3 4 4 5 7 8  - 인덱스(7) 위치 노드 제거
data: 1 2 3 4 4 5 7 8  - 인덱스(0) 위치 노드 제거
data: 1 2 3 4 4 5 7 2 8 - 인덱스(7) 위치 노드에 2 추가

---

간략한 설명

 

Linkedlist 클래스 = head를 가지고 있음(None인 이유는 아직 가리키고 있는게 없기 때문)

method 부분

append

 

append 처음 부분

헤드가 비었을때, 새로운 노드를 헤드가 바로 가리킬 수 있게 만듬

 

cur = self.head 이면

cur의 next가 비어 있지 않는다면,  그다음으로 넘어가기 위해 cur = cur.next 로 만들고

다음 원소가 없으면 새로운 원소가 그 다음 원소가 될 수 있게 작성 

cur.next = Node(data)

 

결국 가장 헤드부터 시작해서 마지막 위치 데이터를 넣어주겠다는 말

 

show

헤드부터 출발하여 노드가 비어있지 않으면 데이터를 하나씩 출력

 

search

헤드부터 출발하여 index 까지 점프해서 index 차례의 노드를 찾는다는 

 

insert

• 특정 인덱스에 노드를 넣을 때 사용

new = Node(data) 를 통해 새로운 노드 추가

 

첫번째 위치를 넣어줄 때 

head 가 새로운 원소를 가리켜야함

new.next = self.head

self.head = new

 

다른경우 삽입시 작성한 search를 통해 삽입 위치의 앞에 노드를 먼저 찾아서 진행

중간에 데이터를 끼워 넣었다고 생각했을때

 

node = self.search(index - 1)

next = node.next : 앞노드의 다음 노드가 next

node.next = new : 새롭게 추가된 노드가 node.next

new.next = next : 추가된 그 다음노드가 new.next, 즉 기존의 추가전 앞노드 다음노드가 next

 

remove

• 특정 인덱스 노드 삭제할 때

첫 위치를 삭제할때

head 가  head다음인 head.next를 가리키게하면됨

 

다른경우 삭제 시 작성한 search를 통해 삽입 위치의 앞에 노드를 먼저 찾아서 진행

front = self.search(index -1) : 앞노드

front.next = front.next.next :

앞노드의 다음 노드는 삭제한 노드 다음에 있는 노드니까 앞노드 다음 다음 노드인 front.next.next 를 가리키게함