연결리스트(Linked List)

학교 알고리즘, 자료구조 수업중 만나게된 연결리스트 네 정체가 궁금하다

연결리스트(Linekd List)란?

핵심 | 연결리스트는 연속된 노드(Node)의 연결체이다.

그럼, 노드란?

연결리스트에서 사용되는 하나의 덩어리로 데이터와 링크를 담고있는 구조이다.
그림으로 먼저 알아보자

여기서 왼쪽에 data, 오른쪽에 next라 적혀있는 부분이 있다.
각 역할을 보면

• data : Data, value(데이터 값이 들어감)
• next : pointer(링크, 포인터 역할로써 다음 노드 주소 저장)

코드로 보게된다면

class Node{
	constructor(data){
		this.data=data;
		this.next=null;
       }
 }

이렇게 구성이되고 next의 연결리스트의 기본 모델로 보게된다면 목적지는 null값이 출력된다.

연결리스트의 종류

• 단순 연결리스트(Singly Linked List)
• 원형 연결리스트(Circular Linked List)
• 이중 연결리스트(Doubly Linked List)

필요 단어 | Head Node(노드의 시작점), Tail Node(노드의 마지막)

각 리스트는 그림으로 보게되면 쉽게 비교된다

단순 연결리스트

단순연결리스트는 처음 노드부터(Head Node) next가 경로를 찾아 다음 노드로 향하게되고 마지막 노드(Tail Node)은 None 값을 출력하게된다.

# Node 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data  # 노드의 값
        self.next = None  # 다음 노드에 대한 포인터

# LinkedList 클래스 정의
class LinkedList:
    def __init__(self):
        self.head = None  # 첫 번째 노드 (head)

    # 리스트의 끝에 노드 추가
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            last = self.head
            while last.next:
                last = last.next
            last.next = new_node

    # 리스트 출력
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 연결 리스트 사용 예시
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.display()  # 10 -> 20 -> 30 -> None

원형 연결리스트

원형연결리스트는 순서대로 next가 다음 노드를 찾아가게되고 마지막 노드(Tail Node)는 처음 노드(Head Nod)로 향하게된다.

# Node 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# CircularLinkedList 클래스 정의
class CircularLinkedList:
    def __init__(self):
        self.head = None

    # 리스트의 끝에 노드 추가
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head  # 자기 자신을 가리키도록 함
        else:
            current = self.head
            while current.next != self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head  # 마지막 노드가 다시 첫 번째 노드를 가리킴

    # 리스트 출력
    def display(self):
        current = self.head
        if self.head is None:
            print("Empty list")
            return
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print("(Back to Head)")

# 원형 연결 리스트 사용 예시
cll = CircularLinkedList()
cll.append(10)
cll.append(20)
cll.append(30)
cll.display()  # 10 -> 20 -> 30 -> (Back to Head)

이중연결리스트

이중연결리스트는 처음 노드부터(Head Node) next가 경로를 찾아 간 후다음 노드로 향하게되고 마지막 노드(Tail Node)에서 거꾸로 돌아온다.

# Node 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data  # 노드의 값
        self.next = None  # 다음 노드에 대한 포인터
        self.prev = None  # 이전 노드에 대한 포인터

# DoublyLinkedList 클래스 정의
class DoublyLinkedList:
    def __init__(self):
        self.head = None  # 첫 번째 노드 (head)

    # 리스트의 끝에 노드 추가 (Append)
    def append(self, data):
        new_node = Node(data)
        if self.head is None:  # 리스트가 비어있을 경우
            self.head = new_node
        else:
            current = self.head
            while current.next:  # 마지막 노드까지 이동
                current = current.next
            current.next = new_node  # 마지막 노드의 다음을 새로운 노드로 설정
            new_node.prev = current  # 새로운 노드의 이전을 현재 노드로 설정

    # 리스트의 앞에 노드 추가 (Prepend)
    def prepend(self, data):
        new_node = Node(data)
        if self.head is None:  # 리스트가 비어있을 경우
            self.head = new_node
        else:
            new_node.next = self.head  # 새로운 노드의 다음을 현재 첫 번째 노드로 설정
            self.head.prev = new_node  # 현재 첫 번째 노드의 이전을 새로운 노드로 설정
            self.head = new_node  # 새로운 노드를 첫 번째 노드로 설정

    # 리스트 출력 (앞에서부터)
    def display_forward(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    # 리스트 출력 (뒤에서부터)
    def display_backward(self):
        current = self.head
        if current is None:
            return
        while current.next:  # 마지막 노드까지 이동
            current = current.next
        while current:  # 마지막 노드에서 첫 번째 노드까지 이동
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")

# 이중 연결 리스트 사용 예시
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.prepend(5)  # 리스트의 앞에 추가

print("Forward traversal:")
dll.display_forward()  # 5 <-> 10 <-> 20 <-> 30 <-> None

print("Backward traversal:")
dll.display_backward()  # 30 <-> 20 <-> 10 <-> 5 <-> None

그럼 배열과 연결리스트의 다른점은 뭘까?

배열과 리스트의 차이점은 그럼으로 보면 더욱 쉽다.

array즉 배열은 하나의 메모리 안에 순서대로 연결되어있다면

linked list는 각노드가 다음 노드의 주소를 찾아가는 모습을 볼 수 있다.

그렇다면 언제 배열과 연결리스트는 뭐가달라?

두 가지의 큰차이점은 하단과 같다.
array

• 배열은 random access 가능
• 배열의 n번째 원소 방문시 O(1)시간으로 가능하다
  ex) arr[3]
• 원소 삽입&삭제시 일반적으로 O(n)시간 소요
  Linked List
• 연결리스트는 random access 불가능
• 연결리스트의 n번째 원소 방문시 O(n)시간으로 가능
  head노드부터 n번째 노드까지 순회하게된다.
• 배열보다 빨라질수있는 노드 삽입 삭제 가능

공부를 위해 기록해두는 글이다보니 틀린점이나 수정부분이 있으면 댓글 부탁드립니다!