링크드 리스트 기본 정리
- 배열은 순차적으로 연결된 공간에 데이터를 나열한다
- 링크드리스트는 떨어진 곳에 화살표를 연결하여 데이터를 나열한다고 생각하면 이해하기 좀 더 쉽다.
- 장점 : 데이터의 저장공간 낭비를 줄일 수 있지만 어떻게 보면 노드 안에 값이 2개가 들어가기 때문에 낭비 요소는 있다.
- 단점 : 접근 속도가 느리다, 중간 데이터 삭제시 이전, 다음 데이터의 연결 작업이 필요하다.
링크드리스트 기본 용어
- 노드 : 데이터의 저장 단위(데이터 값, 포인터)로 구성이 되어있다.
- 포인터 : 다음이나 이전 데이터의 노드값이 들어있다.
public class MySingleNode<T> {
public Node Head = null;
public class Node<T> {
T data;
Node<T> pointer;
public Node(T item) {
this.data = item;
}
}
public void addNode(T data) {
if (Head == null) {
Head = new Node<T>(data);
} else {
Node node = Head;
while (node.pointer != null) {
node = node.pointer;
}
node.pointer = new Node<T>(data);
}
}
public void printAll() {
if (Head != null) {
Node<T> node = this.Head;
System.out.println(node.data);
while(node.pointer != null) {
node = node.pointer;
System.out.println(node.data);
}
}
}
public Node<T> search(T data) {
if (this.Head == null) {
return null;
}
else {
Node<T> node = this.Head;
while (node != null) {
if (node.data == data) {
return node;
} else {
node = node.pointer;
}
}
return null;
}
}
public void addNodeInside(T data, T isData) {
Node<T> searchNode = this.search(isData);
if (searchNode == null) {
addNode(data);
} else {
Node<T> nextNode = searchNode.pointer;
searchNode.pointer = new Node<T>(data);
searchNode.pointer.pointer = nextNode;
}
}
public void MyDeleteNodeInside(T deleteData) {
if(this.Head == null) {
;
} else {
Node<T> node = this.Head;
while (node != null) {
if(node.pointer.data == deleteData) {
node.pointer = node.pointer.pointer;
break;
} else {
node = node.pointer;
}
}
}
}
public boolean delNode(T isData) {
if (this.Head == null) {
return false;
} else {
Node<T> node = this.Head;
if (node.data == isData) {
this.Head = this.Head.pointer;
return true;
} else {
while (node.pointer != null) {
if (node.pointer.data == isData) {
node.pointer = node.pointer.pointer;
return true;
}
node = node.pointer;
}
return false;
}
}
}
public static void main(String[] args) {
MySingleNode<Integer> myList = new MySingleNode<>();
myList.addNode(1);
myList.addNode(2);
myList.addNode(3);
myList.addNodeInside(5,2);
myList.delNode(3);
myList.printAll();
}
}