반응형
더블 링크드 리스트란
싱글 링크드 리스트를 개선한 자료구조.
싱글 링크드 리스트는 단방향 자료구조이고 더블 링크드 리스트는 양방향 자료구조.
헤드에서 테일 방향과 테일에서 헤드 방향으로 찾는 자료 구조입니다.
싱글 링크드 리스트와 다른 점은 이전 노드에 대한 포인터가 생겼다는 차이뿐입니다.
살펴 보기
C 소스
DoublyLinkedList.h
/*
* DoublyLinkedList.h
*
* Created on: 2018. 12. 30.
* Author: otrodevym
*/
#ifndef DOUBLYLINKEDLIST_H_
#define DOUBLYLINKEDLIST_H_
#define NULL (void *)0
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct tagNode{
ElementType Data;
struct tagNode* PrevNode;
struct tagNode* NextNode;
} Node;
Node* DLL_CreateNode(ElementType NewData);
void DLL_DestroyNode(Node* Node);
void DLL_AppendNode(Node** Head, Node* NewNode);
void DLL_InsertAfter(Node* Current, Node* NewNode);
void DLL_RemoveNode(Node** Head, Node* Remove);
Node* DLL_GetNodeAt(Node* Head, int Location);
int DLL_GetNodeCount(Node* Head);
#endif /* DOUBLYLINKEDLIST_H_ */
싱글 링스드 리스트와 다른 점은 tagNode* PreNode;가 있습니다.
DoublyLinkedList.c
#include "./DoublyLinkedList.h"
Node* DLL_CreateNode(ElementType NewData) {
Node* NewNode = (Node*) malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->PrevNode = NULL;
NewNode->NextNode = NULL;
return NewNode;
}
void DLL_DestroyNode(Node* Node) {
free(Node);
}
void DLL_AppendNode(Node** Head, Node* NewNode) {
if ((*Head) == NULL) {
*Head = NewNode;
} else {
Node* Tail = (*Head);
while (Tail->NextNode != NULL) {
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
NewNode->PrevNode = Tail;
}
}
void DLL_InsertAfter(Node* Current, Node* NewNode) {
NewNode->NextNode = Current->NextNode;
NewNode->PrevNode = Current;
if (Current->NextNode != NULL) {
Current->NextNode->PrevNode = NewNode;
}
Current->NextNode = NewNode;
}
void DLL_RemoveNode(Node** Head, Node* Remove) {
if (*Head == Remove) {
*Head = Remove->NextNode;
if ((*Head) != NULL) {
(*Head)->PrevNode = NULL;
}
} else {
Node* Temp = Remove;
if (Remove->PrevNode != NULL) {
Remove->PrevNode->NextNode = Temp->NextNode;
}
if (Remove->NextNode != NULL) {
Remove->NextNode->PrevNode = Temp->PrevNode;
}
}
Remove->NextNode = NULL;
Remove->PrevNode = NULL;
}
Node* DLL_GetNodeAt(Node* Head, int Location) {
Node* Current = Head;
while(Current != NULL && (--Location >=0)){
Current = Current->NextNode;
}
return Current;
}
int DLL_GetNodeCount(Node* Head){
unsigned int Count = 0;
Node* Current = Head;
while(Current != NULL){
Count++;
Current = Current->NextNode;
}
return Count;
}
삭제 부분만 조금 신경 쓰면 됩니다.
업애주는 노드의 다음과 이전을 서로 연결해주면 됩니다.
main.c
#include "./DoublyLinkedList.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char *argv[]) {
int i = 0;
int Count = 0;
Node* List = NULL;
Node* NewNode = NULL;
Node* Current = NULL;
for(i = 0; i < 5; i++){
NewNode = DLL_CreateNode(i);
DLL_AppendNode(&List, NewNode);
}
Count = DLL_GetNodeCount(List);
for(i = 0; i < Count; i++){
Current = DLL_GetNodeAt(List, i);
printf("Data : %d \n ", Current->Data);
}
printf("\n Inserting 3000 After [2]....");
Current = DLL_GetNodeAt(List, 2);
NewNode = DLL_CreateNode(3000);
DLL_InsertAfter(Current, NewNode);
Count = DLL_GetNodeCount(List);
for(i = 0; i < Count; i++){
Current = DLL_GetNodeAt(List, i);
printf("Data : %d \n", Current->Data );
}
printf("\n Destroyng List...\n");
Count = DLL_GetNodeCount(List);
for( i = 0; i < Count; i++){
Current = DLL_GetNodeAt(List, 0);
if(Current != NULL){
DLL_RemoveNode(&List, Current);
DLL_DestroyNode(Current);
}
}
return 0;
}
Java 소스1
기본적인 CRUD를 구현했습니다.
java 소스1, 2차이는 tail여부와 양방향 검색입니다.
DoublyLinkedList.java
package linked_list;
public class DoublyLinkedList<T> {
private int size;
private Node head;
public DoublyLinkedList() {
this.size = 0;
this.head = null;
}
class Node{
private T value;
private Node nextNode;
private Node prevNode;
public Node(T value) {
this.value = value;
this.nextNode = null;
this.prevNode = null;
}
}
public void add(T value) {
Node newNode = new Node(value);
if(this.head == null) {
this.head = newNode;
}else {
Node tail = head;
while(tail.nextNode != null) {
tail = tail.nextNode;
}
tail.nextNode = newNode;
newNode.prevNode = tail;
}
this.size++;
}
public T get(int index) {
Node tail = head;
if(index < 0 || index >= size ) {
throw new NullPointerException("데이터 없음 : " + index);
}else {
while((tail.nextNode != null) && (--index >= 0)) {
tail = tail.nextNode;
}
}
return tail.value;
}
public void remove(int index) {
Node tail = head;
if(index < 0 || index >= size ) {
throw new NullPointerException("데이터 없음 : " + index);
}else {
while(tail.nextNode != null && (--index >=0)) {
tail = tail.nextNode;
}
Node current = tail;
if(null != current.prevNode) {
tail.prevNode.nextNode = current.nextNode;
}
if(null != current.nextNode) {
tail.nextNode.prevNode = current.prevNode;
}
current.nextNode = null;
current.prevNode = null;
current.value = null;
this.size--;
}
}
public void update(int index, T value) {
Node tail = head;
if(index < 0 || index >= size ) {
throw new NullPointerException("데이터 없음 : " + index);
}else{
while(tail.nextNode != null && (--index >= 0)) {
tail = tail.nextNode;
}
tail.value = value;
}
}
public void print() {
for(int i = 0; i < this.size; i++) {
System.out.println(this.get(i));
}
System.out.println("print() ---- end");
}
public static void main(String args[]) {
DoublyLinkedList<String> list = new DoublyLinkedList<>();
list.add("1");
list.add("2");
list.add("3");
list.print();
list.remove(2);
list.update(0,"6");
// list.update(1,"6");
// list.update(2,"6");
list.print();
}
}
Java 소스2
1 2 3 4 5 6 7 8
-> <-
찾고자 하는 위치가 2라면 head에서 출발
찾고자 하는 위치가 6이라면 tail에서 출발
private T get(int index) {
Node search = null;
if (index < 0 || index >= size) {
throw new NullPointerException("데이터 없음 : " + index);
} else if(index < (size /2)){
search = this.head;
while ((search.nextNode != null) && (--index >= 0)) {
search = search.nextNode;
}
}else {
search = this.tail;
while((search.prevNode != null) && (++index < size)) {
search = search.prevNode;
}
}
return search.value;
}
package linked_list;
public class DoublyLinkedList2<T> {
private int size;
private Node head;
private Node tail;
private DoublyLinkedList2() {
this.size = 0;
this.head = null;
this.tail = null;
}
class Node {
private T value;
private Node nextNode;
private Node prevNode;
public Node(T value) {
this.value = value;
this.nextNode = null;
this.prevNode = null;
}
}
private void add(T value) {
Node newNode = new Node(value);
if (this.head == null) {
this.head = newNode;
this.tail = head;
} else {
this.tail.nextNode = newNode;
newNode.prevNode = this.tail;
this.tail = newNode;
}
this.size++;
}
private T get(int index) {
Node search = null;
if (index < 0 || index >= size) {
throw new NullPointerException("데이터 없음 : " + index);
} else if(index < (size /2)){
search = this.head;
while ((search.nextNode != null) && (--index >= 0)) {
search = search.nextNode;
}
}else {
search = this.tail;
while((search.prevNode != null) && (++index < size)) {
search = search.prevNode;
}
}
return search.value;
}
private void remove(int index) {
Node temp = this.head;
if (index < 0 || index >= size) {
throw new NullPointerException("데이터 없음 : " + index);
} else if (index == 0) {
this.head.nextNode.prevNode = null;
this.head = this.head.nextNode;
} else if ((size-1) == index) {
this.tail.prevNode.nextNode = null;
this.tail = this.tail.prevNode;
} else {
while (temp.nextNode != null && (--index > 0)) {
temp = temp.nextNode;
}
Node current = temp;
if (null != current.prevNode) {
temp.prevNode.nextNode = current.nextNode;
}
if (null != current.nextNode) {
temp.nextNode.prevNode = current.prevNode;
}
current.nextNode = null;
current.prevNode = null;
current.value = null;
}
this.size--;
}
private void update(int index, T value) {
Node temp = head;
if (index < 0 || index >= size) {
throw new NullPointerException("데이터 없음 : " + index);
} else {
while (temp.nextNode != null && (--index >= 0)) {
temp = temp.nextNode;
}
temp.value = value;
}
}
private void print() {
for (int i = 0; i < this.size; i++) {
System.out.println(this.get(i));
}
System.out.println("print() ---- end");
}
public static void main(String args[]) {
DoublyLinkedList2<String> list = new DoublyLinkedList2<>();
list.add("1");
list.add("2");
list.add("3");
list.print();
list.remove(2);
list.update(0, "6");
// list.update(1,"6");
// list.update(2,"6");
list.print();
}
}
반응형
'개발(합니다) > 컴퓨터 일반&CS' 카테고리의 다른 글
| [연산자표기법]전위 표기법, 중위 표기법, 후위 표기법 (0) | 2018.12.31 |
|---|---|
| [자료구조] 환형 링크드 리스트(Circular Linked List) (0) | 2018.12.30 |
| [자료구조]싱글 링크드 리스트(Linked List) (0) | 2018.12.30 |
| 정적 메모리, 자동 메모리, 자유 저장소 (0) | 2018.12.28 |
| 함수와 메소드의 차이 (0) | 2018.12.14 |
