반응형
Linked List란
배열의 단점을 해결하고자 만든 자료 구조.
몇개의 배열을 선언 할지 알 수 없기때문에 이를 해결하기 위한 자료 구조.
고리와 고리를 연결한 형태로 나의 다음번째가 누구인지 알고 있는 데이터 구조입니다.
헤드에서 테일 방향으로 찾는 자료 구조입니다.
비엔나 소세지 같은 구조입니다.
살펴보기
링크드 리스트라는 개념 안에는 노드, 헤드 ,테일이 있습니다.
노드란
데이터와 다음을 가르치는 정보를 가지고 있는 단위를 노드라고 합니다.
헤드란
줄을 설 때 어디가 첫 번째인지 알아야 순서를 정할 수 있기 때문에 알아야 합니다.
테일이란
줄을 설 때 마지막 다음에 서야 하기때문에 마지막이 누구인지 알아야 합니다.
C 소스
typedef stuct tagNode{
int Data;
struct tagNode* NextNode;
}
int Data는 Data를 저장 할 변수입니다.
tagNode*는 다음 Node의 주소를 저장 하는 포인터입니다.
tagNode 안에 tagNode 자료형의 NextNode를 선언함으로써 자신과 같은 메모리의 주소를 저장 합니다.
Node* SLL_CreateNode(ElementType NewData){
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->NextNode = NULL;
return NewNode;
}
tagNode1 선언 시 tagNode* NexteNode는 null이고
tagNode2가 추가 되면 tagNode1의 tagNode* NextNode는 tagNode2의 주소를 가지게 됩니다.
void SLL_AppendNode(Node** head, Node* NewNode){
if( (*head) == NULL){
*head = NewNode;
}else{
Node* Tail = (*head);
while(Tail->NextNode != NULL){
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
}
}
Node* tail = (*head);로 함으로써 tail은 head의 주소 값을 가지게 됩니다.
list의 주소를 head가 바라보고 head의 주소를 tail이 바라보는 이중포인터입니다.
list <- head <- tail 입니다.
head는 첫번째 노드를 가르키고 있고 tail은 마지막 노드를 찾기 위해 NextNode가 null 일때까지 꼬리 물기를 합니다.
배열로 예를 들면 예를 들어 1, 2, 3, 4, 5 순서대로 있는 데이터가 있습니다.
↑ ↑
head tail
head의 값을 받은 tail은 1부터 다음 노드 정보를 받아 5번째 노드의 NextNode 주소가 null일 때까지 이동합니다.
main.c
#include <stdio.h>
#include <stdlib.h>
#include "LinkedList.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* Current = NULL;
Node* NewNode = NULL;
for(i = 0; i < 5; i++){
NewNode = SLL_CreateNode(i);
SLL_AppendNode(&List, NewNode);
}
NewNode = SLL_CreateNode(-1);
SLL_InsertNewHead(&List, NewNode);
NewNode = SLL_CreateNode(-2);
SLL_InsertNewHead(&List, NewNode);
Count = SLL_GetNodeCount(List);
for(i = 0; i < Count; i++){
Current = SLL_GetNodeAt(List, i);
printf("List[%d] : %d \n " , i, Current->Data);
}
printf("\n Inserting 3000 After [2]...\n\n]");
Current = SLL_GetNodeAt(List, 2);
NewNode = SLL_CreateNode(3000);
SLL_InsertAfter(Current, NewNode);
Count = SLL_GetNodeCount(List);
for(i = 0; i < Count; i++){
Current = SLL_GetNodeAt(List, i);
printf("List[%d] : %d \n", i , Current->Data);
}
printf("\n Inserting 2000 Before [2]...\n\n]");
Current = SLL_GetNodeAt(List, 1);
NewNode = SLL_CreateNode(2000);
SLL_InsertBefore(&List, Current, NewNode);
Count = SLL_GetNodeCount(List);
for(i = 0; i < Count; i++){
Current = SLL_GetNodeAt(List, i);
printf("List[%d] : %d \n", i , Current->Data);
}
printf("\n Destroying List...\n");
for(i = 0; i < Count; i++){
Current = SLL_GetNodeAt(List, 0);
if(Current != NULL){
SLL_RemoveNode(&List, Current);
SLL_DestroyNode(Current);
}
}
printf("hi");
return 0;
}
LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
typedef int ElementType;
typedef struct tagNode{
ElementType Data;
struct tagBide* NextNode;
} Node;
Node* SLL_CreateNode(ElementType NewData);
void SLL_DestroyNode(Node* Node);
void SLL_AppendNode(Node** Head, Node* NewNode);
void SLL_InsertAfter(Node* Current, Node* NewNode);
void SLL_InsertNewHead(Node** Head, Node* NewHead);
void SLL_RemoveNode(Node** Head, Node* Remove);
Node* SLL_GetNodeAt(Node* Head, int Location);
int SLL_GetNodeCount(Node* Head);
#endif
LinkedList.c
#include "LinkedList.h"
#define NULL (void *)0
Node* SLL_CreateNode(ElementType NewData){
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->NextNode = NULL;
return NewNode;
}
void SLL_DestroyNode(Node* Node){
free(Node);
}
void SLL_AppendNode(Node** head, Node* NewNode){
if( (*head) == NULL){
*head = NewNode;
}else{
Node* Tail = (*head);
while(Tail->NextNode != NULL){
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
}
}
void SLL_InsertNewHead(Node** Head, Node* NewHead){
if( (*Head == NULL)){
(*Head) = NewHead;
}else{
NewHead->NextNode = (*Head);
(*Head) = NewHead;
}
}
void SLL_InsertAfter(Node* Current, Node* NewNode){
NewNode->NextNode = Current->NextNode;
Current->NextNode = NewNode;
}
void SLL_InsertBefore(Node** Head, Node* Current, Node* NewNode){
Node* Tail = (*Head);
while(Tail != NULL && Tail->NextNode != Current){
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
NewNode->NextNode = Current;
// NewNode->NextNode = Tail->NextNode;
}
void SLL_RemoveNode(Node** Head, Node* Remove){
if(*Head == Remove){
*Head = Remove->NextNode;
}else{
Node* Current = *Head;
while( Current != NULL && Current->NextNode != Remove){
Current = Current->NextNode;
}
if(Current != NULL){
Current->NextNode = Remove->NextNode;
}
}
}
Node* SLL_GetNodeAt(Node* Head, int Location){
Node* Current = Head;
while(Current != NULL && (--Location) >= 0){
Current = Current->NextNode;
}
return Current;
}
int SLL_GetNodeCount(Node* Head){
int Count = 0;
Node* Current = Head;
while(Current != NULL){
Current = Current->NextNode;
Count++;
}
return Count;
}
Java 소스1
기본적인 CRUD를 구현했습니다.
java 소스1,2의 차이는 tail여부입니다.
package linked_list;
public class MySinglyLinkedList {
private int size;
private Node head;
private Node tail;
class Node {
private int value;
private Node nextNode;
public Node(int value) {
this.value = value;
this.nextNode = null;
}
}
public void add(int value) {
Node newNode = new Node(value);
if (this.head == null) {
this.head = newNode;
tail = this.head;
} else {
while (tail.nextNode != null) {
tail = tail.nextNode;
}
tail.nextNode = newNode;
}
size++;
}
public int get(int index) {
if (this.head == null || this.size <= index) {
throw new NullPointerException("데이터 없음");
} else {
int count = 0;
while (tail.nextNode != null) {
if (index == count) {
break;
}
tail = tail.nextNode;
count++;
}
}
return tail.value;
}
public boolean delete(int index) {
if (this.size < index) {
return false;
// throw new NullPointerException("데이터 없음");
}
int count = 0;
Node seardh = head;
while (seardh.nextNode != null) {
count++;
if (index == count) {
seardh.nextNode = seardh.nextNode.nextNode;
break;
}
seardh = seardh.nextNode;
}
size--;
return true;
}
public void print() {
Node seardh = head;
while(seardh != null) {
System.out.println(seardh.value);
seardh = seardh.nextNode;
}
}
public void insertAfter(int index, int value) {
Node node = new Node(value);
Node seardh = head;
int count = 0;
while(seardh != null) {
if(index == count) {
node.nextNode = seardh.nextNode;
seardh.nextNode = node;
break;
}
count++;
seardh = seardh.nextNode;
}
}
public void insertBefore(int index, int value) {
Node node = new Node(value);
Node seardh = head;
if(index == 0) {
node.nextNode = seardh;
head = node;
}else {
int count = 0;
while(seardh != null) {
count++;
if(index == count) {
node.nextNode = seardh.nextNode;
seardh.nextNode = node;
break;
}
seardh = seardh.nextNode;
}
}
}
public void update(int index, int value) {
Node seardh = head;
int count = 0;
while(seardh != null) {
if(index == count) {
seardh.value = value;
break;
}
count++;
seardh = seardh.nextNode;
}
}
public static void main(String args[]) {
MySinglyLinkedList list = new MySinglyLinkedList();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);
list.delete(3);
list.insertAfter(0, 100);
list.insertBefore(2, 500);
list.update(4, 600);
list.print();
}
}
Java 소스2
package linked_list;
public class SinglyLinkedList2 {
private int size;
private Node head;
private Node current;
public SinglyLinkedList2() {
this.size = 0;
this.head = null;
this.current = null;
}
class Node {
private int value;
private Node nextNode;
public Node(int value) {
this.value = value;
this.nextNode = null;
}
}
public void add(int value) {
Node newNode = new Node(value);
if (this.head == null) {
this.head = newNode;
this.current = head;
} else {
while (this.current.nextNode != null) {
this.current = this.current.nextNode;
}
this.current.nextNode = newNode;
this.current = newNode;
}
size++;
}
public int get(int index) {
Node current = head;
if (this.head == null || this.size <= index) {
throw new NullPointerException("데이터 없음");
} else {
int count = 0;
while (current.nextNode != null) {
if (index == count) {
break;
}
current = current.nextNode;
count++;
}
}
return current.value;
}
public boolean delete(int index) {
Node current = head;
if (this.size < index) {
return false;
// throw new NullPointerException("데이터 없음");
}
int count = 0;
while (current.nextNode != null) {
count++;
if (index == count) {
current.nextNode = current.nextNode.nextNode;
break;
}
current = current.nextNode;
}
size--;
return true;
}
public void print() {
Node current = head;
while(current != null) {
System.out.println(current.value);
current = current.nextNode;
}
}
public void insertAfter(int index, int value) {
Node node = new Node(value);
Node current = head;
int count = 0;
while(current != null) {
if(index == count) {
node.nextNode = current.nextNode;
current.nextNode = node;
break;
}
count++;
current = current.nextNode;
}
}
public void insertBefore(int index, int value) {
Node node = new Node(value);
Node current = head;
if(index == 0) {
node.nextNode = current;
head = node;
}else {
int count = 0;
while(current != null) {
count++;
if(index == count) {
node.nextNode = current.nextNode;
current.nextNode = node;
break;
}
current = current.nextNode;
}
}
}
public void update(int index, int value) {
Node current = head;
int count = 0;
while(current != null) {
if(index == count) {
current.value = value;
break;
}
count++;
current = current.nextNode;
}
}
public static void main(String args[]) {
SinglyLinkedList2 list = new SinglyLinkedList2();
list.add(10);
list.add(20);
list.add(30);
list.add(40);
list.add(50);
list.delete(3);
list.insertAfter(0, 100);
list.insertBefore(2, 500);
list.update(4, 600);
list.print();
}
}
반응형
'개발(합니다) > 컴퓨터 일반&CS' 카테고리의 다른 글
| [자료구조] 환형 링크드 리스트(Circular Linked List) (0) | 2018.12.30 |
|---|---|
| [자료구조]더블 링크드 리스트(Doubly Linked List) (0) | 2018.12.30 |
| 정적 메모리, 자동 메모리, 자유 저장소 (0) | 2018.12.28 |
| 함수와 메소드의 차이 (0) | 2018.12.14 |
| 점근적 분석과 표기법 : 시간 복잡도와 공간 복잡도 (0) | 2018.12.13 |
