덱, 큐 - 이중 연결 리스트(feat python, Java, JS)
1. 개요
내장된 자료구조 큐를 사용하는데 왜 이렇게 구현하는지 궁금해졌습니다.
- 자바 - 링크드 리스트
- 파이썬 - deque
2. 큐
삽입 - 싱글 연결리스트
싱글 링크드리스트로 큐를 구현하면서 가장 시간이 오래 걸린점은 가장 마지막 노드에 원소를 삽입할때 탐색해야해서 O(n)이 걸렸습니다.
이를 해결하기 위해서 가장 마지막 노드를 tail에 저장하면 되는데 이렇게 할것이면 결국 더블 링크드 리스트로 만들어서, 덱을 만들고, 필요한 기능만 사용하는 것이 유리해보였습니다.
3. 코드
1) Python
class Node:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
class Deque:
def __init__(self):
self.__head = None
self.__tail = None
self.__cnt = 0
def is_empty(self):
return self.__cnt == 0
def size(self):
return self.__cnt
def __increase(self):
self.__cnt += 1
def __decrease(self):
if self.__cnt > 0:
self.__cnt -= 1
def add_first(self, val):
node = Node(val)
self.__head = node
self.__tail = node
self.__increase()
def add_last(self, val):
node = Node(val)
self.__tail.next = node
node.prev = self.__tail
self.__tail = self.__tail.next
self.__increase()
def push(self, val):
if self.is_empty():
self.add_first(val)
else:
self.add_last(val)
def pop_left(self):
if not self.is_empty():
head = self.__head
if self.__head.next:
self.__head = self.__head.next
self.__decrease()
return head.val
else:
return None
def pop(self):
if not self.is_empty():
tail = self.__tail
if tail.prev:
self.__tail = self.__tail.prev
self.__decrease()
return tail.val
else:
return None
def front(self):
return self.__head.val
def last(self):
return self.__tail.val
2) Java
class Node {
public int val;
public Node next;
public Node prev;
public Node(int val) {
this.val = val;
this.next = null;
this.prev = null;
}
}
class Deque {
private Node head;
private Node tail;
private int cnt;
public Dequeue() {
this.head = null;
this.tail = null;
this.cnt = 0;
}
public boolean isEmpty() {
return this.cnt == 0;
}
public int size() {
return this.cnt;
}
public void increase() {
this.cnt++;
}
public void decrease() {
if(this.cnt > 0) this.cnt--;
}
public void addFirst(int val) {
Node node = new Node(val);
this.head = node;
this.tail = node;
this.increase();
}
public void addLast(int val) {
Node node = new Node(val);
this.tail.next = node;
node.prev = this.tail;
this.tail = this.tail.next;
this.increase();
}
public void push(int val) {
if(this.isEmpty()) {
this.addFirst(val);
}
else {
this.addLast(val);
}
}
public Integer popLeft() {
if(!this.isEmpty()) {
Node head = this.head;
if(this.head.next != null) {
this.head = this.head.next;
}
this.decrease();
return head.val;
}
else {
return null;
}
}
public Integer pop() {
if(!this.isEmpty()) {
Node tail = this.tail;
if(tail.prev != null) {
this.tail = this.tail.prev;
}
this.decrease();
return tail.val;
}
else {
return null;
}
}
public Integer front() {
return this.head.val;
}
public Integer last() {
return this.tail.val;
}
}
3) JavaScript
class Node {
constructor(val) {
this.val = val
this.next = null;
this.prev = null;
}
}
class Deque {
constructor() {
this.head = null
this.tail = null
this.cnt = 0
}
isEmpty() {
return this.cnt === 0
}
size() {
return this.cnt
}
increase() {
this.cnt++
}
decrease() {
if(this.cnt > 0) this.cnt--
}
addFirst(val) {
const node = new Node(val)
this.head = node
this.tail = node
this.increase()
}
addLast(val) {
const node = new Node(val)
this.tail.next = node
node.prev = this.tail
this.tail = this.tail.next
this.increase()
}
push(val) {
if(this.isEmpty()) {
this.addFirst(val)
}
else {
this.addLast(val)
}
}
popLeft() {
if(!this.isEmpty()) {
const head = this.head
if(this.head.next) {
this.head = this.head.next
}
this.decrease()
return head.val
}
else {
return null
}
}
pop() {
if(!this.isEmpty()) {
const tail = this.tail
if(tail.prev) {
this.tail = this.tail.prev
}
this.decrease()
return tail.val
}
else {
return null
}
}
front() {
return this.head.val
}
last() {
return this.tail.val
}
}
Author And Source
이 문제에 관하여(덱, 큐 - 이중 연결 리스트(feat python, Java, JS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@skyepodium/덱-큐-이중-연결-리스트feat-python-Java-JS
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
class Node:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
class Deque:
def __init__(self):
self.__head = None
self.__tail = None
self.__cnt = 0
def is_empty(self):
return self.__cnt == 0
def size(self):
return self.__cnt
def __increase(self):
self.__cnt += 1
def __decrease(self):
if self.__cnt > 0:
self.__cnt -= 1
def add_first(self, val):
node = Node(val)
self.__head = node
self.__tail = node
self.__increase()
def add_last(self, val):
node = Node(val)
self.__tail.next = node
node.prev = self.__tail
self.__tail = self.__tail.next
self.__increase()
def push(self, val):
if self.is_empty():
self.add_first(val)
else:
self.add_last(val)
def pop_left(self):
if not self.is_empty():
head = self.__head
if self.__head.next:
self.__head = self.__head.next
self.__decrease()
return head.val
else:
return None
def pop(self):
if not self.is_empty():
tail = self.__tail
if tail.prev:
self.__tail = self.__tail.prev
self.__decrease()
return tail.val
else:
return None
def front(self):
return self.__head.val
def last(self):
return self.__tail.val
class Node {
public int val;
public Node next;
public Node prev;
public Node(int val) {
this.val = val;
this.next = null;
this.prev = null;
}
}
class Deque {
private Node head;
private Node tail;
private int cnt;
public Dequeue() {
this.head = null;
this.tail = null;
this.cnt = 0;
}
public boolean isEmpty() {
return this.cnt == 0;
}
public int size() {
return this.cnt;
}
public void increase() {
this.cnt++;
}
public void decrease() {
if(this.cnt > 0) this.cnt--;
}
public void addFirst(int val) {
Node node = new Node(val);
this.head = node;
this.tail = node;
this.increase();
}
public void addLast(int val) {
Node node = new Node(val);
this.tail.next = node;
node.prev = this.tail;
this.tail = this.tail.next;
this.increase();
}
public void push(int val) {
if(this.isEmpty()) {
this.addFirst(val);
}
else {
this.addLast(val);
}
}
public Integer popLeft() {
if(!this.isEmpty()) {
Node head = this.head;
if(this.head.next != null) {
this.head = this.head.next;
}
this.decrease();
return head.val;
}
else {
return null;
}
}
public Integer pop() {
if(!this.isEmpty()) {
Node tail = this.tail;
if(tail.prev != null) {
this.tail = this.tail.prev;
}
this.decrease();
return tail.val;
}
else {
return null;
}
}
public Integer front() {
return this.head.val;
}
public Integer last() {
return this.tail.val;
}
}
class Node {
constructor(val) {
this.val = val
this.next = null;
this.prev = null;
}
}
class Deque {
constructor() {
this.head = null
this.tail = null
this.cnt = 0
}
isEmpty() {
return this.cnt === 0
}
size() {
return this.cnt
}
increase() {
this.cnt++
}
decrease() {
if(this.cnt > 0) this.cnt--
}
addFirst(val) {
const node = new Node(val)
this.head = node
this.tail = node
this.increase()
}
addLast(val) {
const node = new Node(val)
this.tail.next = node
node.prev = this.tail
this.tail = this.tail.next
this.increase()
}
push(val) {
if(this.isEmpty()) {
this.addFirst(val)
}
else {
this.addLast(val)
}
}
popLeft() {
if(!this.isEmpty()) {
const head = this.head
if(this.head.next) {
this.head = this.head.next
}
this.decrease()
return head.val
}
else {
return null
}
}
pop() {
if(!this.isEmpty()) {
const tail = this.tail
if(tail.prev) {
this.tail = this.tail.prev
}
this.decrease()
return tail.val
}
else {
return null
}
}
front() {
return this.head.val
}
last() {
return this.tail.val
}
}
Author And Source
이 문제에 관하여(덱, 큐 - 이중 연결 리스트(feat python, Java, JS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@skyepodium/덱-큐-이중-연결-리스트feat-python-Java-JS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)