[자료구조]싱글 링크드 리스트(단순 연결 리스트) - 개념 및 생성 & 추가연산

싱글 링크드 리스트(Linked List)

 

싱글 링크드 리스트(Linked List) 개념

• 노드라는 단위의 데이터를 저장하고 데이터가 저장된 각 노드들을 순서대로 연결시켜서 만든 자료구조다.
• 데이터를 순서대로 저장해준다.
• 요소를 계속 추가 할 수 있다.
• 동적배열보다 복잡하다.
• 연결 리스트라고도 부른다.

노드(Node)에는 data, next라는 2가지 속성이 있다.

data에는 저장하고 싶은 정보를 넣는다. next는 다음 노드에 대한 레퍼런스다.

따라서 링크드 리스트는 가장 첫번째의 노드 정보만 알면 next를 타고가서 연결되어 있는 모든 노드를 접근할 수 있다.

첫번째 노드 객체 = head 노드, 마지막 노드 객체 = tail노드

 

*주의*

링크드 리스트는 실제 메모리에 흩어져있는 형식이다.

 

---

예시로 간단한 싱글 링크드 리스트를 만들어 보겠다

class Node:
    """링크드 리스트의 노드 클래스"""
    
    def __init__(self, data):
        self.data = data # 노드가 저장하는 데이터
        self.next = None # 다음 노드에 대한 레퍼런스
        
        
# 데이터 2, 3, 5, 7, 11을 담는 노드들 생성
head_node = Node(2)
node_1 = Node(3)
node_2 = Node(5)
node_3 = Node(7)
tail_node = Node(11)

# 노드들을 연결
head_node.next = node_1
node_1.next = node_2
node_2.next = node_3
node_3.next = tail_node

# 노드 순서대로 출력
iterator = head_node

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next
    

이렇게 만들면 2 3 5 7 11이 차례대로 출력된다.

 

 

---

싱글 링크드 리스트 생성을 해봤으니 이제 싱글 링크드 리스트에서 추가연산을 해보자

class Node:
    """링크드 리스트의 노드 클래스"""
    
    def __init__(self, data):
        self.data = data # 노드가 저장하는 데이터
        self.next = None # 다음 노드에 대한 레퍼런스
        
    
# 링크드 리스트 추가연산
class LinkedList:
    """링크드 리스트 클래스"""
    
    def __init__(self):
        self.head = None
        self.tail = None
        
    def append(self, data):
        """링크드 리스트 추가연산 메소드"""
        new_node = Node(data)
        
        if self.head is None: # 링크드 리스트가 비어있을때
            self.head = new_node
            self.tail = new_node
        else : # 링크드 리스트가 비어있지 않을 때
            self.tail.next = new_node
            self.tail = new_node
            
# 새로운 링크드 리스트 생성
my_list = LinkedList()

# 링크드 리스트에 새로운 데이터 추가
my_list.append(2)
my_list.append(3)
my_list.append(5)
my_list.append(7)
my_list.append(11)

# 링크드 리스트 출력
iterator = my_list.head

while iterator is not None:
    print(iterator.data)
    iterator = iterator.next