자료구조 링크드리스트 -1 by python

이번에는 자료구조 중 링크드 리스트에 대해 알아보자.

---

링크드리스트(Linked List)

1. 의미

링크드리스트에서의 데이터는 데이터뿐만이 아니라 다음 데이터와 연결되어있는 위치 정보(link)도 같이 들어있는 노드(Node)로 구성되어있는 자료구조를 말한다. 링크드리스트의 연결돼있다는 뜻은 이러한 구조에서 나온 것.

 

2. 종류

📄단방향 링크드리스트

   : 가장 기본적인 형태의 링크드리스트. 노드안에 다음 노드로 연결된 링크가 포함되어 있다.

 

📄더블 링크드리스트(이중 연결 리스트)

   : 노드에 이전 데이터로 연결하는 링크를 추가해서 Head만이 아니라 맨 뒤(Tail)부터 데이터를 조회할 수 도 있고, 다시 앞으로 돌아가서 데이터를 조회할 수도 있다.

 

3. 특징

   1) 인덱스가 없고, 현재 데이터 위치에서 이전 및 다음 데이터의 위치를 기억하고 있다.

   2) 1)의 이유로 원하는 데이터를 찾으려면 각 데이터에 부여돼있는 연결 주소를 따라가야만 접근이 가능하다.

   3) 데이터 삽입/삭제 시 해당 데이터 앞뒤에 있는 노드의 연결 주소만 바꿔주면 된다.

 

4. 장점

   1) 데이터 삽입/삭제가 용이하므로 삽입/삭제가 잦은 케이스에서 활용하기 좋다.

5. 단점

   2) 일반 링크드리스트와 같은 경우, 자료를 찾을때마다 첫 노드인 HEAD에서부터 각 노드의 링크를 타고 찾고자 하는 데이터를 찾아야 하므로 데이터 조회가 잦은 케이스에서는 비효율적이다.

 

6. 코드 구현

   링크드리스트는 파이썬 클래스로 구현할 수 있다.

   💻파이썬 일반 링크드리스트 구현💻

class Node:  #노드 인스턴스 생성자만 들어있는 클래스
    def __init__(self, data, next=None): #data값과 next값을 입력하면
        self.data = data #해당 노드의 data값으로 저장된다.
        self.next = next #해당 노드의 다음 링크 값으로 저장된다.
 
class NodeManager:
    def __init__(self, data):  #링크드리스트의 초기 노드 인스턴스를 생성하기위한 생성자 메소드
        self.head = Node(data)
 
    def add(self, data):  #링크드리스트에 새로운 노드를 추가하기위한 메소드
        if self.head == "":  # 혹시 head값이 없을 경우 새로 노드를 하나 추가해서 head로 지정해준다.
            self.head = Node(data)
        else:
            node = self.head  #링크드리스트의 첫 노드를 node라는 변수에 지정
            while node.next:  #node.next가 존재하지않는 노드(마지막 노드)가 나올때까지 다음 노드로 이동하는 반복문
                node = node.next
            node.next = Node(data) #next가 존재하지 않는 새 노드를 생성하고, 
                                    #원래 마지막 노드였던 노드의 next값에 새로 생성한 노드를 지정해준다.
 
    def delete(self, data):
        if self.head = "":        #head가 존재하지않으면 메시지 출력
            print("노드가 존재하지않는 리스트입니다")
        
        if self.head.data == data:    #삭제해야할 노드가 head인 경우
            temp = self.head    #임시 멤버에 head를 지정해 따로 빼놓고
            self.head = self.head.next #원래 head의 다음 노드를 새 head로 지정
            del temp                    #원래 head를 삭제    
        else:    #삭제해야할 노드가 head가 아닌경우
            node = self.head    #node라는 멤버에 head값을 지정
            while node.next:    #node.next 존재여부를 확인하는 반복문
                if node.next.data == data:  #도중에 다음 노드의 data값이 삭제할 노드와 일치하는 경우
                    temp = node.next        #임시멤버에 next값을 지정해 따로 빼놓고
                    node.next = node.next.next #현재 노드의 next값을 삭제할 노드의 다음 노드에 연결
                    del temp  #따로 빼둔 노드를 삭제
                    break
                else:
                    node = node.next
 
    def desc(self): #노드를 Head부터 출력하여 리스트를 확인할 수 있는 메소드 
        node = self.head
        while node.next:
            print(node.data)
            node = node.next

   

   💻단방향 링크드리스트 실제 사용💻

linked_list = NodeManager(0)
linked_list.desc()
 
>> 0
 
linked_list.head
 
>> <__main__.Node at 0x1099fc6a0>  # Head 존재여부 확인
 
linked_list.delete(0)
linked_list.head
 
>> #아무것도 나오지 않음. 정상적으로 삭제됨.
 
for i in range(1, 5):
    linked_list.add(i)
linked_list.desc()
 
>> 1
>> 2
>> 3
>> 4
 
linked_list.delete(2)
 
linked_list.desc()
 
>> 1
>> 3
>> 4

 

   💻단방향 링크드리스트로 구현해본 스택 pop 메소드💻

    def pop(self):
        if self.head = "":
            print("노드가 존재하지 않는 리스트입니다")
 
        else:
            node = self.head
            while node.next.next: #node.next.next가 존재하지않는 노드까지 가는 반복문
                node = node.next
 
            print(node.next.data) #해당 노드의 data멤버 출력 후 
            del node.next

 

😂 여담

이번 기회에 객체지향 코드를 처음 만져봤는데 링크드리스트 자체의 개념은 그리 어렵지 않지만 이걸 객체지향 프로그래밍으로 구현해내는게 너무 어려웠다.

더블 링크드 리스트는 다음 포스팅에서 구현해보도록 하겠다.