티스토리 뷰
노드와 노드가 양방향으로 연결되어 있는 자료구조이다.
각 노드는 value를 저장하는 부분, 이전노드(previous, head방향)와 다음노드(next, tail방향)를 가리키는 부분이 있다.
Doubly Linked List는 아래와 같은 모양으로 구현이 된다.
단방향인 단순 Linked List에 비해 양방향이므로 저장공간이 더 필요하다.
linked list의 front에는 head가 있고, linked list의 마지막에는 tail이 있다.
1. 삽입
push_front
- head쪽에 노드를 추가한다
- 기존노드prev와 새로운노드next와 연결시킨다.
- head와 새로운 node를 연결 시킨다.
push_back
- tail쪽에 노드를 추가한다
- 기존노드next와 새로운노드prev를 연결시킨다.
- tail과 새로운 노드를 연결시킨다.
2. 삭제
pop_front
- head쪽의 노드를 삭제한다
- 가장 앞의 node와 그 다음 node의 연결을 해제한다.
- head와 그 다음 node와 연결한다
- 가장 앞에 있었던 node를 삭제한다.
pop_back
- tail쪽의 노드를 삭제한다.
- 가장 뒤의 노드의 그 전 node의 연결을 해제한다.
- 그 전 node와 tail을 연결한다.
- 가장 뒤에 있었던 노드를 해제한다.
코드로 구현 해보자 (예시코드는 typescript)
1. 노드
value, prev, next로 이루어 진다.
class DoublyLinkedListNode<T>{
public value : T;
public prev : DoublyLinkedListNode<T> | null;
public next : DoublyLinkedListNode<T> | null;
constructor(value : T) {
this.prev = null;
this.value = value;
this.next = null;
}
}2. push_front()
리스트의 가장 앞에 노드를 삽입한다.
public push_front(value : T) : DoublyLinkedListNode<T> {
const newHead = new DoublyLinkedListNode<T>(value);
if(this.head === null){
this.tail = newHead;
}else{
this.head.prev = newHead;
newHead.next = this.head;
}
this.head = newHead;
this.length++;
return newHead;
}1. parameter로 value를 받아온다.
2. value를 이용한 DoublyLinkedListNode를 생성한다.
3. 현재 List의 head를 가리키고 있는것이
- 없을 경우(list에 노드가 없는상태일 경우) : tail에 생성한 노드를 가리키도록 한다.
- 있을 경우 4번으로 넘어감
4. 현재 List의 head노드의 prev가 새로운 노드를 가리키도록 한다.
5. 새로운 노드의 next는 현재 List의 가장 앞에 있던 노드를 가리키도록한다.
6. 현재 List의 head와 새로운 노드를 연결한다.
3. push_back()
리스트의 가장 뒤에 노드를 삽입한다.
public push_back(value : T) : DoublyLinkedListNode<T>{
let newTail = new DoublyLinkedListNode<T>(value);
if(this.tail === null){
this.head = newTail;
}else{
this.tail.next = newTail;
newTail.prev = this.tail;
}
this.tail = newTail;
this.length++;
return newTail;
}1. parameter로 value를 받아온다.
2. value를 이용한 DoublyLinkedListNode를 생성한다.
3. 현재 List의 tail을 가리키고 있는것이
- 없을 경우(list에 노드가 없는상태일 경우) : head에 생성한 노드를 가리키도록 한다.
- 있을 경우 4번으로 넘어감
4. 현재 List의 tail노드의 next가 새로운 노드를 가리키도록 한다.
5. 새로운 노드의 prev는 현재 List의 가장 뒤에 있던 이전 노드를 가리키도록한다.
6. 현재 List의 tail과 새로운 노드를 연결한다.
4. pop_front
public pop_front() : DoublyLinkedListNode<T>{
if(this.head === null) return null;
if(this.head.next === null){
this.tail = null;
}else{
this.head.next.prev = null;
this.head = this.head.next
}
if(this.length > 0) this.length--;
return this.head;
}1. head와 연결된 노드가 없으면(리스트가 없는경우) return
2. 가장 앞의 노드의 next가
- 없다면(노드가 하나만 존재) 노드의 연결을 해제한다.
- 있다면 3번으로 넘어감 (노드가 하나이상 존재)
3. 가장 앞의 노드의 prev를 해제하여 head와의 연결을 해제한다.
4. head를 가장 앞의 노드의 next가 가리키는 노드(가장 마지막에서 1칸 이전의 노드)와 연결한다.
5. pop_back()
public pop_back(){
if(this.tail === null) return null;
if(this.tail.prev === null){
this.head = null;
}else{
this.tail.prev.next = null;
this.tail = this.tail.prev;
}
if(this.length > 0) this.length--;
return this.tail;
}1. tail과 연결된 노드가 없으면(리스트가 없는경우) return
2. 가장 뒤의 노드의 prev가
- 없다면(노드가 하나만 존재) 노드의 연결을 해제한다.
- 있다면 3번으로 넘어감 (노드가 하나이상 존재)
3. 가장 마지막 노드의 next를 해제하여 tail과의 연결을 해제한다.
4. tail을 가장 마지막노드의 prev가 가리키는 노드(가장 마지막에서 1칸 이전의 노드)와 연결한다.
typescript 코드
class DoublyLinkedListNode<T>{
public value : T;
public prev : DoublyLinkedListNode<T> | null;
public next : DoublyLinkedListNode<T> | null;
constructor(value : T) {
this.prev = null;
this.value = value;
this.next = null;
}
}
class DoublyLinkedList<T>{
private head : DoublyLinkedListNode<T> | null;
private tail : DoublyLinkedListNode<T> | null;
public length : number;
constructor(){
this.head = null;
this.tail = null;
this.length = 0;
}
public push_front(value : T) : DoublyLinkedListNode<T> {
const newHead = new DoublyLinkedListNode<T>(value);
if(this.head === null){
this.tail = newHead;
}else{
this.head.prev = newHead;
newHead.next = this.head;
}
this.head = newHead;
this.length++;
return newHead;
}
public push_back(value : T) : DoublyLinkedListNode<T>{
let newTail = new DoublyLinkedListNode<T>(value);
if(this.tail === null){
this.head = newTail;
}else{
this.tail.next = newTail;
newTail.prev = this.tail;
}
this.tail = newTail;
this.length++;
return newTail;
}
public pop_front() : DoublyLinkedListNode<T> | null{
if(this.head === null) return null;
if(this.head.next === null){
this.tail = null;
}else{
this.head.next.prev = null;
this.head = this.head.next
}
if(this.length > 0) this.length--;
return this.head;
}
public pop_back(){
if(this.tail === null) return null;
if(this.tail.prev === null){
this.head = null;
}else{
this.tail.prev.next = null;
this.tail = this.tail.prev;
}
if(this.length > 0) this.length--;
return this.tail;
}
public get(i: number): T | undefined{
if(i > this.length) return undefined;
let curData: DoublyLinkedListNode<T> | null = this.head;
for(let n = 0; n < i; n++){
if(curData) curData = curData?.next;
}
return curData?.value;
}
public display(){
if(this.length === 0) return;
let curNode = this.head;
while(curNode?.next){
console.log(curNode.value);
curNode = curNode.next;
}
console.log(curNode?.value);
}
}
rust 코드
#[derive(Debug)]
struct DoublyLinkedListNode<T>{
val : T,
prev : Option<Rc<RefCell<DoublyLinkedListNode<T>>>>,
next : Option<Rc<RefCell<DoublyLinkedListNode<T>>>>
}
impl<T> DoublyLinkedListNode<T>{
fn new(val : T) -> Rc<RefCell<DoublyLinkedListNode<T>>>{
Rc::new(RefCell::new(DoublyLinkedListNode{
val,
prev : None,
next : None,
}))
}
}
#[derive(Debug)]
struct DoublyLinkedList<T> {
head: Option<Rc<RefCell<DoublyLinkedListNode<T>>>>,
tail: Option<Rc<RefCell<DoublyLinkedListNode<T>>>>,
length: usize
}
impl<T> DoublyLinkedList<T> where T: Copy{
fn new() -> Self{
DoublyLinkedList{
head: None,
tail: None,
length: 0
}
}
fn len(&self) -> usize{
self.length
}
fn push_front(&mut self, val: T) -> Rc<RefCell<DoublyLinkedListNode<T>>>{
let new_head = DoublyLinkedListNode::new(val);
match &self.head.take(){
Some(old_head) => {
old_head.borrow_mut().prev = Some(Rc::clone(&new_head));
new_head.borrow_mut().next = Some(Rc::clone(&old_head));
},
_ => {
self.tail = Some(Rc::clone(&new_head));
}
}
self.head = Some(Rc::clone(&new_head));
self.length += 1;
new_head
}
fn push_back(&mut self, val: T) -> Rc<RefCell<DoublyLinkedListNode<T>>> {
let new_tail = DoublyLinkedListNode::new(val);
match &self.tail.take(){
Some(old_tail) => {
old_tail.borrow_mut().next = Some(Rc::clone(&new_tail));
new_tail.borrow_mut().prev = Some(Rc::clone(&old_tail));
},
_=>{
self.head = Some(Rc::clone(&new_tail));
}
}
self.tail = Some(Rc::clone(&new_tail));
self.length += 1;
new_tail
}
fn pop_front(&mut self) -> Option<T>{
match &self.head.take(){
Some(head_node) => {
match head_node.borrow_mut().next.as_mut(){
Some(next_node) =>{
next_node.borrow_mut().prev = None;
self.head = Some(Rc::clone(&next_node));
},
_ =>{
self.tail = None
}
}
self.length -= 1;
Some(head_node.borrow().val)
},
_ => None
}
}
fn pop_back(&mut self) -> Option<T>{
match &self.tail.take() {
Some(tail_node) => {
match tail_node.borrow_mut().prev.as_mut(){
Some(prev_node) => {
prev_node.borrow_mut().next = None;
self.tail = Some(Rc::clone(&prev_node));
},
_ => {
self.head = None;
}
}
self.length -= 1;
Some(tail_node.borrow().val)
},
_ => None
}
}
fn remove(&mut self, node: Rc<RefCell<DoublyLinkedListNode<T>>>) -> T{
if node.borrow().prev.is_none() && node.borrow().next.is_none(){
self.head = None;
self.tail = None;
self.length = 0;
return node.borrow().val;
}
let mut rn = node.borrow_mut();
match rn.prev.take() {
Some(prev_node) => {
match rn.next.take(){
Some(next_node) => {
prev_node.borrow_mut().next = Some(Rc::clone(&next_node));
next_node.borrow_mut().prev = Some(prev_node);
},
_ => {
prev_node.borrow_mut().next = None;
self.tail = Some(prev_node);
}
}
},
_ => {
self.head = rn.next.clone();
self.head.as_mut().unwrap().borrow_mut().prev = None;
}
}
self.length -= 1;
rn.val
}
}C++ 코드
(리스드 노드 내부에 접근하고 싶으면 DoublyLinkedList의 private에 있는 head, tail을 public으로 내려서 확인하거나, head, tail에 접근하는 함수를 DoublyLinkedList class내에 작성하면 된다.)
template<class T>
struct DoublyLinkedListNode {
T value;
DoublyLinkedListNode<T>* prev;
DoublyLinkedListNode<T>* next;
DoublyLinkedListNode(T val) : value(val), prev(nullptr), next(nullptr) {}
};
template<class T>
class DoublyLinkedList {
private:
DoublyLinkedListNode<T>* head;
DoublyLinkedListNode<T>* tail;
public:
unsigned int length;
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
length = 0;
}
~DoublyLinkedList() {
while (head) {
pop_front();
}
delete head;
delete tail;
}
void push_front(T val) {
DoublyLinkedListNode<T>* newHead = new DoublyLinkedListNode<T>(val);
if (head == nullptr) tail = newHead;
else {
head->prev = newHead;
newHead->next = head;
}
head = newHead;
length++;
}
void push_back(T val) {
DoublyLinkedListNode<T>* newTail = new DoublyLinkedListNode<T>(val);
if (tail == nullptr) head = newTail;
else {
tail->next = newTail;
newTail->prev = tail;
}
tail = newTail;
this->length++;
}
void pop_front() {
if (head == nullptr) return;
if (head->next == nullptr) tail = nullptr;
else {
head->next->prev = nullptr;
head = head->next;
}
if (length > 0) length--;
}
void pop_back() {
if (tail == nullptr) return;
if (this->tail->prev == nullptr) this->head = nullptr;
else {
tail->prev->next = nullptr;
tail = tail->prev;
}
if (length > 0) length--;
}
void remove(DoublyLinkedListNode<T>* node) {
if (node.prev == nullptr && node.next == nullptr) {
head = nullptr;
tail = nullptr;
length = 0;
return;
}
if (node->prev == nullptr) {
head = node->next;
tail = node->prev;
}
else {
node->prev->next->next = node->prev->next;
node->prev->next->prev = node->prev;
}
if (length > 0) length--;
}
};'Computer Science > 알고리즘_자료구조' 카테고리의 다른 글
| [자료구조] BST(Binary Search Tree, 이진탐색트리) (0) | 2021.06.17 |
|---|---|
| [알고리즘] 위상 정렬(Topology Sort) (0) | 2021.06.01 |
| [자료구조] Hash Table (0) | 2021.05.14 |
| [자료구조] 2진트리 탐색 코드 (0) | 2021.04.20 |
| Big-O Notation (0) | 2021.03.12 |