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

연결 리스트 (Linked List)

• 데이터가 연속된 공간에 저장되어 있지 않고, 떨어져 있더라도 연속된 공간에 저장되어 있도록 하는 리스트
• 동적으로 새로운 노드를 삽입하거나 삭제하기 간편하다
• 연결구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 된다
• 데이터를 구조체로 묶어 포인터로 연결되어 있다
• 배열과 달리 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 한다

연결 리스트 핵심요소

• Node : 연결 리스트의 기본 단위
• 데이터 필드 : 노드에 저장된 데이터
• 링크 필드 : 다음 노드를 가르킨다
• Head : 연결 리스트에서 가장 처음 위치하는 노드, 리스트 전체를 참조하는데 사용
• Tail : 연결 리스트에서 가장 마지막에 위치하는 노드, Tail 노드의 링크 필드는 Null을 저장하고 있다

 

연결 리스트 구현 (Python)

class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None
 
class LinkedList:
	def __init__(self):
    	self.head = None
        
    def append(self, data):
        ## 노드가 존재하지 않으면 첫번째 노드(head) 생성
    	if not self.head:
            self.head = Node(data)
        else:
            current = self.head
            ## 노드의 링크 필드가 None이 나올때까지 조회
            while current.next:
            	current = current.next
            ## 링크 필드가 None이면 다음 노드로 저장
            current.next = Node(data)
            
    def print_list(self):
    	current = self.head
    	while current.next:
        	print(current.data)
            current = current.next

 

연결 리스트 삽입, 삭제 구현 (Python)

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

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

...

    def insert(self, data, position):
        new_node = Node(data)
        ## 삽입 노드가 head일 때
        if position == 0:
            new_node.next = self.head
            self.head = new_node
        else:
            current = self.head
            ## 찾으려는 노드의 앞 노드 찾기
            for _ in range(position - 1):
                if current:
                    current = current.next
                else:
                    raise IndexError("position is out of range")
            if current is None:  ## append로 마지막 노드 삽입 가능
                raise IndexError("position is out of range")
            ## 노드 삽입
            else:
                new_node.next = current.next
                current.next = new_node
                
    def delete(self, data):
        ## 삭제 노드가 head일 경우
        if self.head and self.head.data == data:
            self.head = self.head.next
        else:
            current = self.head
            ## 삭제 노드를 찾을때까지 탐색
            while current and current.next and current.next.data != data:
                current = current.next
            ## 삭제하려는 노드의 이전 노드와 그 다음 노드를 이어줌
            if current and current.next:
                current.next = current.next.next
            else:
                raise ValueError("Value is not found in list")

 

참고

1-5. [자료구조이론] Linked List (연결 리스트)

 

(C언어) 연결 리스트(1)(노드의 정의,생성,연결) [자료구조]

 

GitHub - onlybooks/python-algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성