728x90
개요
- LinkedList원리
- Node를 통해서 객체들을 연결을 한 상태로 Node 내부에 data와 nextNode 주소, prevNode 주소 등이 들어갈 수 있다.
- 구현된 LinkedList 이용시 중간에 값 추가, 중간 값 삭제 등 배열보다 높은 성능을 보여준다.
- LinkedList 구현의 필요성
- 회전하는 순서 같이 LinkedList의 원리로 구현할 수 있는 부분들이 LinkedList에 구현이 되어있지 않다.
- ex) 1,2,3 이 저장된 list를 get(int index)을 통해서 뽑아낼때 indexrk list Node 수보다 많으면 예외발생
- 이 외에도 LinkedList를 직접 구현해야되는 상황이 생길시 구현을 할 줄 알아야한다.
- 회전하는 순서 같이 LinkedList의 원리로 구현할 수 있는 부분들이 LinkedList에 구현이 되어있지 않다.
- 구현 순서
- LinkedList : 평소에 사용하는 LinkedList와 동일
- CircleLinkedList : 마지막 Node next에 첫 Node의 주소 넣음
- DoubleLinkedList : prev Node를 추가하여 이전으로 돌아가는 기능을 수행
- CircleDoubleLinkedList 구현 : 첫 Node의 prev에 마지막 Node 주소를 넣고 마지막 Node next에 첫 Node의 주소 넣음
- 전체 코드
- https://github.com/taewan625/java/commits/main
- LinkedListImpl_1step code부터 확인
1. LinkedList 구현
- 구현
public class LinkedListImpl {
public static void main(String[] args) {}
}
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
@Override
public String toString() {
return data + "";
}
}
class LinkedList {
Node head;
public LinkedList() {
this.head = null;
}
public void add(int data) {
Node newNode = new Node(data); // head부터 시작해서 .next가 null일 때 해당 주소를 넣을 것이다.
// 처음 노드가 없을 때 setting
if (head == null) {
head = newNode;
return;
}
// tmp라는 Node에 임시적으로 head 주소를 넣어서 .next가 null일 때 까지 계속 주소값을 덮어 쓸 것이다.
Node tmp = head;
// node객체의 .next가 null일 때까지 .next에 저장되어있는 node객체주소로 tmp주소를 변경
while (tmp.next != null) {
tmp = tmp.next;
}
// tmp 참조변수 안에는 실제 Node 객체의 주소가 들어있다. 그래서 tmp.next에 값을 넣어주면 실제 객체의 .next 값이 변한다.
tmp.next = newNode;
}
Node get(int index) {
Node curr = head;
if (index == 0) {
// System.out.println("curr = " + curr);
return curr;
}
for (int i = 1; i <= index; i++) {
curr = curr.next;
}
// System.out.println("curr = " + curr);
return curr;
}
}
- TDD
class LinkedListTest {
boolean LinkedListImpl(int a, int b) {
LinkedList list = new LinkedList();
// list 개수 추가
for (int i = 0; i < a; i++) {
list.add(i);
}
// 5번째 Node의 toString 값
// Linked되어있지 않으면 예외가 터진다. Linked되어있으면 true 반환
// a>=b인 경우만 true, - 마지막 Node의 next가 null이기 때문
for (int i = 0; i < b; i++) {
list.get(i);
}
return true;
}
@Test
void addCorrect() {
assertTrue(LinkedListImpl(8, 4));
assertTrue(LinkedListImpl(8, 8));
assertTrue(LinkedListImpl(8, 1));
assertTrue(LinkedListImpl(1, 1));
// True인 이유는 마지막 노드는 null 다음 Node로 연결하기 때문
assertTrue(LinkedListImpl(7, 8));
}
@Test
void addOverNum(){
assertThrows(NullPointerException.class, () -> LinkedListImpl(1, 8));
assertThrows(NullPointerException.class, () -> LinkedListImpl(6, 8));
}
}
2. CircleLinkedList
- 구현
class LinkedList {
private Node head;
private Node tail;
public LinkedList() {
this.head = null;
}
public void add(int data) {
Node newNode = new Node(data); // head부터 시작해서 .next가 null일 때 해당 주소를 넣을 것이다.
// 처음 노드가 없을 때 setting
if (head == null) {
head = newNode; // 동일 Node 객체 주소가짐
tail = newNode; // 동일 Node 객체 주소가짐
newNode.next = head; // .next에 처음 Node 주소 저장
}else {
tail.next = newNode; // tail.next에 새로운 Node 객체 주소로 변경 -> tail과 head는 같은 주소를 가지므로 head.next값도 변경됨
tail = newNode; // tail과 연결된 객체 주소를 최신 것으로 변경
tail.next = head; // 변경된 객체의 .next는 현재 null인 상태 -> 다시 처음 객체 주소인 head와 연결시켜서 circle 만듬
}
}
- TDD
class LinkedListTest {
boolean LinkedListImpl(int a, int b) {
LinkedList list = new LinkedList();
// list 개수 추가
for (int i = 0; i < a; i++) {
list.add(i);
}
for (int i = 0; i < b; i++) {
list.get(i);
}
return true;
}
@Test
// linked 끝이 처음과 연결되어서 a < b 여도 정상 작동
void addOverNumCircle() {
assertTrue(LinkedListImpl(1, 8));
assertTrue(LinkedListImpl(6, 8));
}
}
3. DoubleLinkedList
- 구현
class Node {
int data;
Node next;
Node prev;
public Node(int data) {
this.data = data;
@@ -32,11 +33,10 @@ public void add(int data) {
if (head == null) {
head = newNode; // 동일 Node 객체 주소가짐
tail = newNode; // 동일 Node 객체 주소가짐
}else {
tail.next = newNode; // tail.next에 새로운 Node 객체 주소로 변경 -> tail과 head는 같은 주소를 가지므로 head.next값도 변경됨
newNode.prev = head; // 변경된 객체의 .next는 현재 null인 상태 -> 다시 처음 객체 주소인 head와 연결시켜서 circle 만듬
tail = newNode; // tail과 연결된 객체 주소를 최신 것으로 변경
}
}
Node get(int index) {
Node curr = head;
if (index == 0) {
return curr;
}
for (int i = 1; i <= index; i++) {
curr = curr.next;
}
return curr;
}
}
- TDD
class LinkedListTest {
boolean LinkedListImpl(int a, int b) {
LinkedList list = new LinkedList();
// list 개수 추가
for (int i = 0; i < a; i++) {
list.add(i);
}
for (int i = 0; i < b; i++) {
list.get(i);
}
// 내림차순 생성
for (int i = b; i < 0; i--) {
list.get(i);
}
return true;
}
@Test
void addCorrect() {
assertTrue(LinkedListImpl(8, 4));
assertTrue(LinkedListImpl(8, 8));
assertTrue(LinkedListImpl(8, 1));
assertTrue(LinkedListImpl(1, 1));
assertTrue(LinkedListImpl(7, 8));
}
@Test
void addOverNum(){
assertThrows(NullPointerException.class, () -> LinkedListImpl(1, 8));
assertThrows(NullPointerException.class, () -> LinkedListImpl(6, 8));
}
}
4. CircleLinkedList
- 구현
public void add(int data) {
Node newNode = new Node(data); // head부터 시작해서 .next가 null일 때 해당 주소를 넣을 것이다.
// 처음 노드가 없을 때 setting
if (head == null) {
head = newNode; // 동일 Node 객체 주소가짐
tail = newNode; // 동일 Node 객체 주소가짐
}else {
newNode.prev = tail;
tail.next = newNode; // tail.next에 새로운 Node 객체 주소로 변경 -> tail과 head는 같은 주소를 가지므로 head.next값도 변경됨
tail = newNode; // tail과 연결된 객체 주소를 최신 것으로 변경
}
tail.next = head; // tail의 Node주소는 계속 newNode로 변경되고 next를 head 주소로 연결하므로 마지막 칸에서 다시 처음으로 돌아옴
head.prev = tail; // 반대로 head의 이전Node 주소를 newNode로 연결하면 첫칸에서 마지막으로 잘 넘어감
}
- TDD
@Test
void addCorrect() {
assertTrue(LinkedListImpl(8, 4));
assertTrue(LinkedListImpl(8, 8));
assertTrue(LinkedListImpl(8, 1));
assertTrue(LinkedListImpl(1, 1));
assertTrue(LinkedListImpl(7, 8));
}
@Test
// linked 끝이 처음과 연결되어서 a < b 여도 정상 작동
void addOverNumCircle() {
assertTrue(LinkedListImpl(1, 8));
assertTrue(LinkedListImpl(6, 8));
}