단일 연결 리스트 (Singly Linked List)

단일 연결 리스트 (Singly Linked List)

단일 연결 리스트(Singly Linked List)는 선형 자료 구조 중 하나로, 각 노드가 하나의 데이터 요소와 다음 노드를 가리키는 포인터를 포함하는 형태로 구성된다. 연결 리스트는 배열과 달리 요소들이 메모리상에 연속적으로 배치되지 않으며, 각 노드가 다음 노드를 가리키고 있어 동적 메모리 할당이 가능하다.

구조

• 노드 (Node): 연결 리스트의 기본 구성 요소로, 데이터와 다음 노드를 가리키는 포인터를 포함한다.
  • 데이터 (Data): 노드가 저장하는 값.
  • 다음 (Next): 다음 노드를 가리키는 포인터.
• 헤드 (Head): 리스트의 첫 번째 노드를 가리키는 포인터. 리스트의 시작점이다.
• 꼬리 (Tail): 리스트의 마지막 노드를 가리키는 포인터 (단일 연결 리스트에서는 일반적으로 사용되지 않음).

단일 연결 리스트의 연산

1. 삽입 (Insertion):
   • 앞쪽 삽입 (Insert at the Beginning): 새 노드를 헤드 앞에 추가하고, 헤드를 새 노드로 갱신한다.
   • 끝쪽 삽입 (Insert at the End): 새 노드를 리스트의 끝에 추가한다.
   • 중간 삽입 (Insert in the Middle): 특정 위치에 새 노드를 삽입한다.
2. 삭제 (Deletion):
   • 앞쪽 삭제 (Delete from the Beginning): 첫 번째 노드를 삭제하고, 헤드를 다음 노드로 갱신한다.
   • 끝쪽 삭제 (Delete from the End): 마지막 노드를 삭제한다.
   • 중간 삭제 (Delete in the Middle): 특정 위치의 노드를 삭제한다.
3. 탐색 (Search): 리스트를 순회하면서 특정 값을 가진 노드를 찾는다.
4. 길이 반환 (Get Length): 리스트에 포함된 노드의 개수를 반환한다.
5. 출력 (Display): 리스트의 모든 노드를 순서대로 출력한다.

단일 연결 리스트의 활용 예

1. 동적 메모리 할당: 메모리의 크기를 동적으로 조정할 수 있어, 크기가 가변적인 데이터 구조를 만들 수 있다.
2. 구현 용이성: 삽입과 삭제가 용이하여, 자주 삽입과 삭제가 일어나는 응용 프로그램에서 사용된다.
3. 기타 자료 구조의 기반: 스택, 큐, 덱 등 다른 자료 구조의 구현에 기반이 될 수 있다.

단일 연결 리스트의 장단점

장점:

1. 동적 크기 조정: 배열과 달리 리스트의 크기를 동적으로 조정할 수 있다.
2. 삽입 및 삭제 연산의 용이성: 리스트의 특정 위치에서의 삽입과 삭제가 빠르게 이루어질 수 있다.

단점:

1. 임의 접근 불가: 배열과 달리 임의의 인덱스로 접근하는 데 시간이 오래 걸린다 (O(n)).
2. 추가 메모리 사용: 각 노드가 데이터 외에도 다음 노드를 가리키는 포인터를 저장해야 하므로 추가 메모리를 사용한다.

구현 코드

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

    def setNext(self, next):
        self._next = next

    def getNext(self):
        return self._next

    def getData(self):
        return self._data

class SinglyLinkedList:
    def __init__(self):
        self._head = None

    def insertBeginning(self, data):
        new_node = Node(data)
        new_node.setNext(self._head)
        self._head = new_node

    def insertEnd(self, data):
        new_node = Node(data)
        if self._head is None:
            self._head = new_node
            return
        last = self._head
        while last.getNext():
            last = last.getNext()
        last.setNext(new_node)

    def insertMiddle(self, data, index):
        if index < 0:
            print("Invalid position")
            return
        new_node = Node(data)
        if index == 0:
            new_node.setNext(self._head)
            self._head = new_node
            return
        cur = self._head
        for i in range(index - 1):
            if cur is None:
                print("Index out of bounds")
                return
            cur = cur.getNext()
        if cur is None:
            print("Index out of bounds")
            return
        new_node.setNext(cur.getNext())
        cur.setNext(new_node)

    def deleteNode(self, key):
        temp = self._head

        if temp is not None:
            if temp.getData() == key:
                self._head = temp.getNext()
                temp = None
                return

        while temp is not None:
            if temp.getData() == key:
                break
            prev = temp
            temp = temp.getNext()

        if temp == None:
            return

        prev.setNext(temp.getNext())
        temp = None

    def search(self, key):
        cur = self._head
        while cur is not None:
            if cur.getData() == key:
                return True
            cur = cur.getNext()
        return False

    def getLength(self) -> int:
        count = 0
        cur = self._head
        while cur:
            count += 1
            cur = cur.getNext()
        return count

    def display(self):
        cur = self._head
        while cur:
            print(cur.getData(), end=" -> ")
            cur = cur.getNext()
        print("None")

sll = SinglyLinkedList()
sll.insertEnd(10)
sll.insertEnd(20)
sll.insertBeginning(5)
sll.insertMiddle(15, 2)  # Insert 15 at position 2
sll.display()  # 5 -> 10 -> 15 -> 20 -> None
print(sll.search(10))  # True
print(sll.getLength())  # 4
sll.deleteNode(10)
sll.display()  # 5 -> 15 -> 20 -> None

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms