Single Linked List

# Single Linked List

 Linked List는 노드라는 객체로 구성되어 있습니다. 

노드는 데이터를 저장할 수 있는 필드와 다음 노드를 가리킬 수 있는 포인터 필드를 가지고 있습니다. 이 노드들이 다 연결된 리스트를 Linked List라고 하게 됩니다. 가장 앞 노드를 Head, 가장 뒤의 노드를 Tail이라고 하며, Tail은 다음 노드가 없기 때문에 포인터는 Null을 가리키게 됩니다.

array list와는 다르게 Linked List는 인덱스를 통한 random access가 불가능 합니다.

자신을 가리키고 있는 포인터만을 통해서 접근할 수 있기 때문에 N개의 노드를 가지고 있는 리스트는 O(N)의 시간이 소요됩니다. 

 

# 코드 구현 (python)

우선 노드를 만들어주는 클래스를 생성합니다

class Node:
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node   
    # 노드의 데이터값 리턴해주는 함수    
    def get_data(self):
        return self.data
    # 노드의 다음 노드를 리턴해주는 함수
    def get_next(self):
        return self.next_node
    # 노드의 다음 노드를 지정해주는 함수(포인터)
    def set_next(self, new_next):
        self.next_node = new_next

dummy node ( 데이터없이 존재하는 노드 )를 통해 구현하겠습니다.

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

 

[ add ]

추가 기능은 tail 노드 앞에 노드를 추가합니다. tail노드까지 찾아서 가야 하기 때문에 O(N)의 시간이 소요됩니다.

def add(self, data):
    curr = self.head
    while curr.get_next() != None:
        curr = curr.get_next()
    new_node = Node(data)
    curr.set_next(new_node)
    self.size += 1

    curr = self.head                         
    while curr.get_next() != None:
        curr = curr.get_next()              head에서 부터 마지막노드까지 타고 들어감
    

    new_node = Node(data)
    curr.set_next(new_node)            원래 리스트의 마지막 노드(curr)의 다음 노드로 new node를 지정
    self.size += 1

 

[ insert ]

중간에 삽입할 때는 Array List와는 다르게 데이터들을 다 미뤄줄 필요없이 간단하게 포인터만 바꿔주면 쉽게 삽입이 가능합니다. 이 때도 마찬가지로 삽입할 자리를 찾아가기위한 과정에서 O(N)의 시간이 소요됩니다.

def insert(self, idx, data):
    if idx < 0 or idx > self.size:
        raise Exception("Invalid Index")
    i = 0
    prev = self.head
    curr = prev.get_next()   
    i += 1
    while i < idx:
        prev = prev.get_next()
        curr = curr.get_next()
    new_node = Node(data)
    prev.set_next(new_node)
    new_node.set_next(curr)
    self.size += 1

    if idx < 0 or idx > self.size:
        raise Exception("Invalid Index")      입력한 인덱스가 전체 길이보다 크면 예외 발생
    i = 0
    prev = self.head                     head를 이전노드
    curr = prev.get_next()            head다음 노드를 curr(인덱스 노드가 됨)
    i += 1
    while i < idx:                          
        prev = prev.get_next()
        curr = curr.get_next()         위치를 찾아감
    

    new_node = Node(data)         새로운 노드 생성
    prev.set_next(new_node)      prev와 new_node 연결
    new_node.set_next(curr)      new_node와 curr 연결
    self.size += 1

 

[delete] & [delete by index]

delete기능은 입력한 데이터 값으로 삭제하고, delete by index는 입력한 인덱스의 데이터를 삭제합니다. 삭제할 떄도 삽입과 마찬가지로 데이터들을 다 땡겨올 필요없이 간단하게 포인터만 바꿔주고 원래 연결을 끊어주면 됩니다.

def delete(self, data):
    prev = self.head
    curr = prev.get_next()
    while curr != None:
        if curr.get_data() == data:
            prev.set_next(curr.get_next())
            curr.set_next(None)
            self.size -= 1
        prev = prev.get_next()
        curr = curr.get_next()

    prev = self.head
    curr = prev.get_next()
    while curr != None:             마지막노드까지

        if curr.get_data() == data:                 입력한 데이터를 찾으면
            prev.set_next(curr.get_next())      이전 노드와 다음 노드 연결
            curr.set_next(None)                     원래 연결을 끊어줌
            self.size -= 1
        prev = prev.get_next()
        curr = curr.get_next()       위치 찾아 가기

def deletebyindex(self, idx):
    if idx < 0 or idx >= self.size:
        raise Exception("Invalid Index")
    i = 0
    prev = self.head
    curr = prev.get_next()
    i += 1
    while i < idx:
        prev = prev.get_next()
        curr = curr.get_next()
    prev.set_next(curr.get_next())
    curr.set_next(None)
    self.size -= 1
    return True

 

# 전체 코드

전체코드와 다른 기능들은 깃허브를 참고하시면 됩니다.

https://github.com/sonzwon/TIL/blob/master/data_structure_List.py

GitHub - sonzwon/TIL: Today I Learned