[코딩 테스트] 6일차: 연결 리스트

연결 리스트

연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 자료구조입니다. 배열과 달리 연결 리스트는 메모리상에서 연속적으로 저장되지 않습니다.

단일 연결 리스트

단일 연결 리스트는 각 노드가 다음 노드에 대한 포인터만을 가지고 있는 리스트입니다.

JavaScript에서의 단일 연결 리스트 구현

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

class LinkedList {
  constructor() {
    this.head = null;
  }

  // 노드 추가
  append(data) {
    let newNode = new Node(data);
    if (this.head === null) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }
    current.next = newNode;
  }

  // 노드 출력
  printList() {
    let current = this.head;
    let list = "";
    while (current !== null) {
      list += current.data + " -> ";
      current = current.next;
    }
    list += "null";
    console.log(list);
  }
}

let list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // "10 -> 20 -> 30 -> 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):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    # 노드 출력
    def print_list(self):
        current = self.head
        list_str = ""
        while current:
            list_str += str(current.data) + " -> "
            current = current.next
        list_str += "None"
        print(list_str)

list = LinkedList()
list.append(10)
list.append(20)
list.append(30)
list.print_list() # "10 -> 20 -> 30 -> None"

이중 연결 리스트

이중 연결 리스트는 각 노드가 다음 노드와 이전 노드에 대한 포인터를 가지고 있는 리스트입니다.

JavaScript에서의 이중 연결 리스트 구현

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // 노드 추가
  append(data) {
    let newNode = new Node(data);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }
    this.tail.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
  }

  // 노드 출력
  printList() {
    let current = this.head;
    let list = "";
    while (current !== null) {
      list += current.data + " <-> ";
      current = current.next;
    }
    list += "null";
    console.log(list);
  }
}

let list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // "10 <-> 20 <-> 30 <-> null"

Python에서의 이중 연결 리스트 구현

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

class DoublyLinkedList:
    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
            return
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node

    # 노드 출력
    def print_list(self):
        current = self.head
        list_str = ""
        while current:
            list_str += str(current.data) + " <-> "
            current = current.next
        list_str += "None"
        print(list_str)

list = DoublyLinkedList()
list.append(10)
list.append(20)
list.append(30)
list.print_list() # "10 <-> 20 <-> 30 <-> None"

순환 리스트

순환 리스트는 마지막 노드가 첫 번째 노드를 가리키는 리스트입니다.

JavaScript에서의 순환 리스트 구현

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

class CircularLinkedList {
  constructor() {
    this.head = null;
  }

  // 노드 추가
  append(data) {
    let newNode = new Node(data);
    if (this.head === null) {
      this.head = newNode;
      newNode.next = this.head;
      return;
    }
    let current = this.head;
    while (current.next !== this.head) {
      current = current.next;
    }
    current.next = newNode;
    newNode.next = this.head;
  }

  // 노드 출력
  printList() {
    if (this.head === null) {
      return;
    }
    let current = this.head;
    let list = "";
    do {
      list += current.data + " -> ";
      current = current.next;
    } while (current !== this.head);
    list += "head";
    console.log(list);
  }
}

let list = new CircularLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // "10 -> 20 -> 30 -> head"

Python에서의 순환 리스트 구현

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

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

    # 노드 추가
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
            return
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head

    # 노드 출력
    def print_list(self):
        if self.head is None:
            return
        current = self.head
        list_str = ""
        while True:
            list_str += str(current.data) + " -> "
            current = current.next
            if current == self.head:
                break
        list_str += "head"
        print(list_str)

list = CircularLinkedList()
list.append(10)
list.append(20)
list.append(30)
list.print_list() # "10 -> 20 -> 30 -> head"

연습 문제

문제 1: 연결 리스트에서 중복 요소 제거

주어진 단일 연결 리스트에서 중복된 요소를 제거하는 프로그램을 작성하세요.

JavaScript

function removeDuplicates(linkedList) {
  let current = linkedList.head;
  let seen = new Set();
  let prev = null;

  while (current !== null) {
    if (seen.has(current.data)) {
      prev.next = current.next;
    } else {
      seen.add(current.data);
      prev = current;
    }
    current = current.next;
  }
}

let list = new LinkedList();
list.append(10);
list.append(20);
list.append(20);
list.append(30);
removeDuplicates(list);
list.printList(); // "10 -> 20 -> 30 -> null"

Python

def remove_duplicates(linked_list):
    current = linked_list.head
    seen = set()
    prev = None

    while current:
        if current.data in seen:
            prev.next = current.next
        else:
            seen.add(current.data)
            prev = current
        current = current.next

list = LinkedList()
list.append(10)
list.append(20)
list.append(20)
list.append(30)
remove_duplicates(list)
list.print_list() # "10 -> 20 -> 30 -> None"

문제 2: 이중 연결 리스트의 노드 삭제

이중 연결 리스트에서 주어진 값을 가진 첫 번째 노드를 삭제하는 프로그램을 작성하세요.

JavaScript

class DoublyLinkedList {
  // ... 이전 코드 생략 ...

  deleteNode(data) {
    let current = this.head;

    while (current !== null) {
      if (current.data === data) {
        if (current.prev !== null) {
          current.prev.next = current.next;
        } else {
          this.head = current.next;
        }
        if (current.next !== null) {
          current.next.prev = current.prev;


        } else {
          this.tail = current.prev;
        }
        return;
      }
      current = current.next;
    }
  }
}

let list = new DoublyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.deleteNode(20);
list.printList(); // "10 <-> 30 <-> null"

Python

class DoublyLinkedList:
    # ... 이전 코드 생략 ...

    def delete_node(self, data):
        current = self.head

        while current:
            if current.data == data:
                if current.prev:
                    current.prev.next = current.next
                else:
                    self.head = current.next
                if current.next:
                    current.next.prev = current.prev
                else:
                    self.tail = current.prev
                return
            current = current.next

list = DoublyLinkedList()
list.append(10)
list.append(20)
list.append(30)
list.delete_node(20)
list.print_list() # "10 <-> 30 <-> None"

결론

이번 글에서는 코딩 테스트 준비를 위해 단일 연결 리스트, 이중 연결 리스트, 순환 리스트에 대해 배웠습니다. 이를 통해 다양한 연결 리스트의 개념과 구현 방법을 익힐 수 있었습니다. 다음 글에서는 트리와 그래프에 대해 알아보겠습니다.

다음 글에서 만나요!