chorock.page
소개글시리즈프로젝트실험
© 2026 chorock.page
← 목록으로
자료구조 · 5/5
← 이전 글
자료구조python

연결된 구조(LinkedList)

2026.11.17 · 7분 읽기 · 조회 0

목차
연결된 구조란?연결된 구조의 특징연결 리스트의 구조연결 리스트의 종류단순연결리스트 응용: 연결된 스택삽입 연산 push()삭제 연산 pop()연결 리스트의 크기 size()peek(), display()단순연결리스트 응용: 연결 리스트getNode()getEntry()replace()find()삽입 연산: insert(pos, elem)삭제 연산: delete(pos)원형연결리스트의 응용: 연결된 큐연결된 큐 클래스삽입 연산: enqueue()삭제 연산: dequeue()size()display()이중연결리스트로 구현한 덱이중연결리스트를 위한 노드연결된 덱 클래스addFront()addRear()deleteFront()deleteRear()

연결된 구조란?

연결된 구조는 흩어진 데이터를 링크로 연결해서 관리한다.

배열 구조(array)

  • 모든 항목들이 연속된 메모리 공간에 저장된다.
  • 인덱스를 이용해 항목들에 접근한다.

연결된 구조 (linked-list)

  • 각 항목들이 메모리에 흩어져 저장됨
  • 링크(link)를 이용하여 다음 항목으로 접근한다
  • 노드(node) = 데이터 + 링크(다음 노드를 가리킴)

연결된 구조의 특징

  • 용량이 고정되지 않는다.

  • 중간에 자료를 삽입하거나 삭제하는 것이 용이하다.
    -> 시간 복잡도: O(1)

  • n번째 항목에 접근은 시간이 오래 걸린다.
    -> 시간 복잡도: O(n)

연결 리스트의 구조

노드

  • 데이터 필드(data field): 항목(값)을 저장
  • 하나 이상의 링크 필드(link field): 다음 노드를 가리킴

헤드 포인터(head pointer)

  • 첫 번째 노드의 주소를 저장

연결 리스트의 종류

단순 연결 리스트(singly linked list)

원형 연결 리스트(circular linked list)

이중 연결 리스트(doubly linked list)

단순연결리스트 응용: 연결된 스택

  • 노드 클래스
python
class Node:                               # 단순 연결리스트를 위한 노드 클래스
    def __init__(self, elem, link=None):  # 생성자. 디폴트 인수 사용
      self.data = elem                    # 데이터 멤버 생성 및 초기화
      self.link = link                    # 링크 생성 및 초기화
  • 연결된 스택 클래스
python
class LinkedStack:
    def __init__(self):  # 생성자
      self.top = None    # top 생성 및 초기화
    
    def isEmpty(self): return self.top == None # 공백상태 검사
    def clear(self): self.top = None           # 스택 초기화

삽입 연산 push()

python
def push(self, item):
    n = Node(item, self.top) # 노드의 다음 링크로 self.top을 줌
    self.top = n
  1. 입력 데이터 E를 이용해 새로운 노드 n을 생성함 : n = Node(E)
  2. n의 링크가 시작노드를 가리키도록 함: n.link = top
  3. top이 n을 가리키도록 함: top = n

삭제 연산 pop()

python
def pop(self):
    if not self.isEmpty():  # 공백이 아니면
        n = self.top        # 현재 top 노드의
        self.top = n.link   # 다음 노드를 top으로 지정
        return n.data       # 이전의 top 데이터 반환
  1. 변수 n이 시작노드를 가리키도록 함: n = top
  2. top이 다음노드를 가리키도록 함: top = n.link
  3. n이 가리키는 노드의 데이터를 반환함: return n.data

연결 리스트의 크기 size()

  • size()
    -> 연결된 리스트의 모든 노드의 개수를 구해야 함
    -> 전체 노드를 순회함
python
def size(self):
    node = self.top   # top에서 시작
    count = 0
    while not node == None:   # 노드가 None이 될 때 까지
      node = node.link        # 다음 노드로 이동
      count += 1              # count 증가
    return count

peek(), display()

python
def peek(self):
    if not self.isEmpty():
        return self.top.data
 
def display(self, msg=`LinkedStack : `):
    print(msg, end="")
    node = self.top    # top에서 시작
    while not node == None:     # 노드가 없을 때 까지
      print(node.data, end=' ') # 노드 출력
      node = node.link          # 다음 노드로 이동
    print()

단순연결리스트 응용: 연결 리스트

  • 삽입, 삭제가 임의의 위치에서도 가능
  • 노드 클래스: 연결된 스택과 동일
python
class LinkedList:
    def __init__(self):
      self.head = None
    
    def isEmpty(self): return self.head == None  # 공백상태 검사
    def clear(self): self.head = None            # 리스트 초기화
    
    def size(self):
        node = self.head   # head에서 시작
        count = 0
        while not node == None:   # 노드가 None이 될 때 까지
          node = node.link        # 다음 노드로 이동
          count += 1              # count 증가
        return count
 
    def display(self, msg=`LinkedStack : `):
        print(msg, end="")
        node = self.head            # head에서 시작
        while not node == Node:     # 노드가 없을 때 까지
          print(node.data, end=' ') # 노드 출력
          node = node.link          # 다음 노드로 이동
        print()

getNode()

  • pos 번째 노드 반환: getNode(pos)
python
def getNode(self, pos):
    if pos < 0: return None  # 음수면 None 리턴
    node = self.head         # head부터 시작
    while pos > 0 and node != None:   # pos 번 반복
      node = node.link                # 다음 노드로 이동
      pos -= 1
    return node                       # 최종 노드 반환

getEntry()

  • pos 번째 노드의 데이터 반환: getEntry(pos)
python
def getEntry(self, pos):
    node = self.getNode(pos)
    if node == None: return None
    else: return node.data

replace()

  • 특정 위치의 데이터를 변경: replace(pos, ele)
python
def replace(self, pos, ele):
    if pos < 0: pos = 0
    if pos >= self.size(): pos = self.size() - 1
    node = self.getNode(pos)
    node.data = ele

find()

  • 원하는 데이터를 가진 노드를 반환: find(data)
python
def find(self, data):
    node = self.head                        # head부터 시작
    while node is not None:
        if node.data == data: return node   # 데이터가 같으면 노드 반환
        node = node.link                    # 다음 노드로 이동
    return node                             # 다 돌면 None 반환

삽입 연산: insert(pos, elem)

4가지 경우를 고려해야 한다.

  1. 빈 리스트에 삽입
  2. 맨 앞에 삽입
  3. 중간에 삽입
  4. 맨 뒤에 삽입
python
def insert(self, pos, elem):
    before = self.getNode(pos-1)  # 삽입 위치 바로 앞 노드 찾기
    if before == None:            # 앞 노드가 없으면
        self.head = Node(elem, self.head)  # 맨 앞에 삽입
    else:
        node = Node(elem, before.link)  # before의 다음 노드를 가리키게 함
        before.link = node         # before가 새 노드를 가리키게 함
  1. 노드 N이 C를 가리키게 함: node.link = before.link
  2. 노드 B가 노드 N을 가리키게 함: before.link = node

삭제 연산: delete(pos)

4가지 고려 사항이 있다.

  1. 빈 리스트에 삭제
  2. 맨 앞 삭제(노드가 하나일 때, 두 개 이상일 때)
  3. 중간 삭제
  4. 맨 뒤 삭제
python
def delete(self, pos):
    before = self.getNode(pos-1)    # 이전 노드 찾기
    if before == None:              # 이전 노드가 없음 -> 맨 앞 노드 삭제
        if self.head is not None:   # 리스트가 비어 있지 않으면
            self.head = self.head.link  # head를 다음 노드로 연결
    elif before.link != None:           # 삭제할 노드가 실제로 존재하면
        before.link = before.link.link  # 삭제할 노드를 건너뛰고 연결
  1. before의 link가 삭제할 노드의 다음 노드를 가리키도록 함: before.link = before.link.link

원형연결리스트의 응용: 연결된 큐

  • 단순연결리스트로 구현한 큐
  • 원형연결리스트로 구현한 큐

    -> 큐의 삽입 위치(맨뒤)가 tail
    -> tail의 바로 다음이 머리이므로 front == tail.link

연결된 큐 클래스

python
class CircularLinkedQueue:
    def __init__(self):
      self.tail = None    # tail: 유일한 데이터
    
    def isEmpty(self): return self.tail == None
    def clear(self): self.tail = None    # 큐 초기화
    def peek(self):
        if not self.isEmpty():
            return self.tail.link.data    # front의 데이터 반환

삽입 연산: enqueue()

python
def enqueue(self, item):
    node = Node(item, None)    # 노드 생성
    if self.isEmpty():         # 큐가 공백일 때
        node.link = node       # 자기자신을 링크
        self.tail = node
    else:                            # 큐가 공백이 아니면
        node.link = self.tail.link   # 노드의 링크를 front에 연결
        self.tail.link = node        # 이전의 tail 다음 노드를 새 노드로 변경
        self.tail = node             # 새 노드를 tail로 변경

삭제 연산: dequeue()

python
def dequeue(self):
    if not self.isEmpty():           # 큐가 공백이 아닐 때
    data = self.tail.link.data       # data = front의 데이터
    if self.tail.link == self.tail:  # front == tail일 때(노드가 1개)
      self.tail = None               # tail 삭제
    else:                            # 노드가 2개 이상일 때
      self.tail.link = self.tail.link.link  # front = front의 다음 노드
    return data                      # 이전의 front 데이터 반환

size()

python
def size(self):
    if self.isEmpty(): return 0
    else:
      count = 1                      # 1부터 시작
      node = self.tail.link          # front 부터 출발
      while not node == self.tail:   # node가 rear가 아닌 동안
        node = node.link             # 다음 노드로 이동
        count += 1                   # count 증가
      return count

display()

python
def display(self, msg=`CircularLinkedQueue`):
    print(msg, end="")
    if not self.isEmpty():
        node = self.tail.link         # front 부터 시작
        while not node == self.tail:  # rear를 만날 때 까지
            print(node.data, end=" ")
            node = node.link
        print(node.data, end=" ")     # 마지막 노드의 항목 출력
    print()

이중연결리스트로 구현한 덱

이중연결리스트를 위한 노드

python
class DNode:
  def __init__(self, elem, prev = None, next = None):
    self.data = elem
    self.prev = prev
    self.next = next

연결된 덱 클래스

python
class DoublyLinkedDeque:
  def __init__(self):
    self.front = None
    self.rear = None
    
  def isEmpty(self): return self.front == None  # front가 None이면 공백
  def clear(self): self.front = self.rear = None  # 전부 초기화
 
 
  def size(self):
    node = self.front   # front에서 시작
    count = 0
    while not node == None:   # 노드가 None이 될 때 까지
      node = node.next        # 다음 노드로 이동
      count += 1              # count 증가
    return count
 
  def display(self, msg=`LinkedStack : `):
    print(msg, end="")
    node = self.front           # front에서 시작
    while not node == None:     # 노드가 없을 때 까지
      print(node.data, end=' ') # 노드 출력
      node = node.next          # 다음 노드로 이동
    print()

addFront()

python
def addFront(self, item):
  node = Dnode(item, None, self.front)
  if self.isEmpty():  # 공백이면
    self.front = self.rear = node  # front와 rear가 모두 node
  else:
      self.front.prev = node  # front의 이전값이 node
      self.front = node       # front 값이 node

addRear()

python
def addRear(self, item):
  node = Dnode(item, self.rear, None)
  if self.isEmpty():                  # 공백이면
    self.front = self.rear = node   # front와 rear가 전부 새 노드
  else:
    self.rear.next = node           # rear의 다음 값 = node
    self.rear = node                # rear를 node로 변경

deleteFront()

python
def deleteFront(self):
  if not self.isEmpty():          # 공백이 아닐 때
    data = self.front.data        # data에 front 값 복사
    self.front = self.front.next  # front를 다음 노드로 변경
    if self.front = None:         # 노드가 하나 뿐이면
      self.rear = None            # rear도 None으로 변경
    else:
      self.front.prev = None    # front의 이전노드 제거
    return data

deleteRear()

python
def deleteRear(self):
  if not self.isEmpty():         # 공백이 아닐 때
    data = self.rear.data        # data에 rear 값 복사
    self.rear = self.rear.prev   # rear를 이전 노드로 변경
    if self.rear = None:         # 노드가 하나 뿐이면
      self.front = None
    else:
      self.rear.next = None      # rear 다음 노드 제거
    return data  
초록
초록

앱과 웹을 만들고, 직접 운영하며 기록합니다.

댓글

giscus로 동작하며 GitHub Discussions에 저장됩니다.

관련 글

자료구조python자료구조

큐(queue) - ADT, BFS

2026.10.16·4분 읽기·조회 0
자료구조python자료구조

스택(Stack) - ADT, 응용, DFS

2026.10.15·11분 읽기·조회 0
자료구조python자료구조

리스트(List) : ADT, Array, Linked-List

2026.10.13·5분 읽기·조회 0

목차

연결된 구조란?연결된 구조의 특징연결 리스트의 구조연결 리스트의 종류단순연결리스트 응용: 연결된 스택삽입 연산 push()삭제 연산 pop()연결 리스트의 크기 size()peek(), display()단순연결리스트 응용: 연결 리스트getNode()getEntry()replace()find()삽입 연산: insert(pos, elem)삭제 연산: delete(pos)원형연결리스트의 응용: 연결된 큐연결된 큐 클래스삽입 연산: enqueue()삭제 연산: dequeue()size()display()이중연결리스트로 구현한 덱이중연결리스트를 위한 노드연결된 덱 클래스addFront()addRear()deleteFront()deleteRear()