[자료구조] Linked List

아마도개발자·2022년 9월 4일
1

자료구조

목록 보기
4/4

개요

리스트의 개념을 가볍게 훑고
타입스크립트리스트 스택을 구현해 볼 것 입니다.

내용

리스트와 링크드 리스트의 특징

  • 리스트는 배열의 특징인 index라는 개념이 존재하지 않습니다.
  • 리스트는 배열과 다르게 사이즈의 제한이 없습니다.
  • 리스트는 데이터를 나열한 구조입니다.
  • 링크드 리스트는 노드라는 요소로 구성 되어있습니다.
  • Node란 밑의 그림에서 data와 link 둘 다 가지고 있는 하나의 단위 입니다.
  • 맨 처음 Node를 Head, 마지막 Node를 Tail이라고 표현 합니다.
  • link는 다음 Node를 가리킵니다. 그래서 마지막 Node는 가리킬 것이 없기 때문에 null이 됩니다.

Linked List를 이용한 Stack

class Node<T> {
	private data: T;
	link: Node<T> | null | undefined;

	constructor(value: T, link: Node<T> | null | undefined) {
		this.data = value;
		this.link = link;
	}

	public getData(): T {
		return this.data;
	}
}

class Stack<T> {
  private top: Node<T> | null | undefined;

  constructor() {
    this.top = null;
  }

  isEmpty(): boolean {
    return this.top === null;
  }

  push(value: T): void {
    const newNode = new Node(value, this.top);
    this.top = newNode;
  }

  pop(): T | null | undefined {
    if (this.isEmpty()) {
      throw new Error("스택이 비어있습니다.");
    }

    const returnNode = this.top;
    this.top = returnNode?.link;
    return returnNode ? returnNode.getData() : null;
  }
}

테스트

const stack = new Stack();

try {
  stack.pop();
} catch (e) {
  console.log(e);
}

stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());

결과

Error: 스택이 비어있습니다.
3
2
1
```![](https://velog.velcdn.com/images/kcdmlry/post/3a86eb67-002c-498b-bd16-badd01af9699/image.png)
profile
분야상관 없이 관심 가는 것을 공부 하고 남깁니다

0개의 댓글