목차
Linked List
쓰게 된 배경
만약 배열과 같이 저장할 수 있는 공간이 한정적이라면 공간이 더 필요할 때 추가하기 어려움
배열은 중간 값을 지울 때 노가다임.
ex) 1:10 의 4를 지울 때 1,3 // 5,10을 각각 따로 복사해서 다시 배열에 저장
정의
Linked List 구조는 데이터를 임의로 늘리고 줄이는데 최적화된 구조
- 각 데이터를 연결고리처럼 연결
- 새로운 데이터가 추가되면 해당 데이터를 가장 마지막 고리에 연결
- 어느 방향이든 삽입/삭제가 편리한 구조
장단점
구조
Node: 실제 데이터와 + node를 연결할 연결 고리 
구현
1) 이러한 작업을 수행할 프로젝트를 만들자 프로젝트와 클래스 생성법
[file]-[new]-[project]
프로젝트 이름은 ListProject
2) Node 클래스를 만들자 [file]-[new]-[class]
클래스 이름은 Node
이번에는 public static void를 체크하지 말자
이 한 묶음이 노드다. 이를 구현해 보자
[구현]
Node next; 연결고리(이어질 다음 저잘 공간의 주소를 가르킬 변수)
int data; 실제 데이터(이 노드에 저장 될 데이터)
public class Node {
// 실제 데이터를 저장할 공간하고 그 데이터 공간을 서로 연결할 고리를 만들어보겠습니다.
Node next; // 연결고리(이어질 다음 저잘 공간의 주소를 가르킬 변수)
int data; // 실제 데이터(이 노드에 저장 될 데이터)
}
3) LinkedList
그럼 이 node들을 연결하는 행동을 관리하는 클래스를 만들어보자
[file]-[new]-[class]
클래스 이름은 LinkedList
이번에도 public static void를 체크하지 말자
LinkedList 구현
새로운 노드를 생성하여 기존의 노드에 링크하는 함수
[1]
최초의 노드, 즉 시작점부터 구현
private Node head = null; 여기에 계속 다른 노드들을 붙여나갈 것이다.
(1.1)
앞의 Node 클래스를 이용해 인스턴트 newBlock 생성 후,
이 newBlock 이라는 다음 노드를 가리키는 코드구현
public void insert(int data)
{
// 새로운 노드를 인스턴스로 만듦
Node newBlock = new Node();
// 인스턴트 안의 변수 선언(노드 값)
newBlock.data = data;
// 다음 노드 가리키는 화살표 구현
head.next = newBlock;
}
즉 여기 화살표 구현
(1.2)
그런데 노드가 연결되어 있는 상황에선 마지막 노드에 연결되어야함
위의 head.next = newBlock;
는 계속 첫번째 블록 뒤에 썼다 지웠다 하는 거죠?
그래서 head에서 연결된 노드들에게 마지막인지 물어보고
마지막이면 그 뒤에 연결
_마지막 노드면 next가 비어 있을 것이다
while(current.next != null)
{
current = current.next;
}
current.next = newBlock;
(1.3)
그런데 head가 null일 때 문제가 생김
기존 블록이 하나도 없을 때 처리하는 특별한 삼수 만들어 줘야함
아무것도 없을 때 시작 블록을 생성해 주는 함수 구현
즉 head가 아무것도 없는 null상태에서 첫 블록으로 구현되는 것
if(head == null)
{
head = newBlock;
return;
}
(전체구현)
새로운 노드를 생성하여 기존의 노드에 링크하는 함수
// 마직막 블록과 이르려면 마지막블록을 찾아야함
// 그러기위해선 첫 번쨰 놈을 알아야함
// 실제 데이터를 저장할 공간하고 그 데이터 공간을 서로 연결할 고리를 만들어보겠습니다.
// 최초의 노드, 시작점 구현
private Node head = null;
public void insert(int data)
{
// 새로운 노드를 인스턴스로 만듦
Node newBlock = new Node();
// 인스턴트 안의 변수 선언(노드 값)
newBlock.data = data;
//
if(head == null)
{
head = newBlock;
return;
}
//head 부터 시작
Node current = head;
// current가 곧 head
// 노드의 next가 비어있지 않으면 계속 다음 블럭으로 가서 next를 확인한다
while(current.next != null)
{
current = current.next;
}
// 마지막이면 while문 빠져나와 그 next에 주소를 붙인다.(연결한다)
current.next = newBlock;
}
출력 함수
[2.1]
각 노드에 담겨있은 데이터 출력하는 함수
public void print()
{
Node current = head;
while(current != null)
{
System.out.println(current.data);
current = current.next;
}
[2.2]
특정 값 출력
public int getData(int idx)
{
Node current = head;
for(int i = 0;i<idx;i++)
current = current.next;
return current.data;
}
노드 사이 삽입
만약 6에 끼워넣고 싶다면
1) 6까지 감
for(int i = 0;i<idx;i++)
current = current.next;
2) 6은 끼워 넣는 노드를 끼워 넣는 노드는 8을 가리키게 함
Node temp = current.next;
current.next = newBlock;
newBlock.next = temp;
[구현]
public void insertAt(int idx, int data)
{
Node newBlock = new Node();
newBlock.data = data;
// 추가할 위치까지 간다
Node current = head;
for(int i = 0;i<idx;i++)
current = current.next;
Node temp = current.next;
current.next = newBlock;
newBlock.next = temp;
}
head 값 바꾸기
public void insertHead(int data)
{
Node newBlock = new Node();
newBlock.data = data;
newBlock.next = head;
head = newBlock;
}
맨 마지막 값 지우기
// 맨 마지막 값 지우기
public void deleteLast()
{
// 노드가 없으면
if(head == null)
return;
Node current = head;
while(current.next.next != null)
current = current.next;
current.next = null;
}
특정 값 지우기
public void deleteAt(int idx)
{
if(head == null)
return;
else if(idx == 0)
{
// head 를 지울꺼에요.
head = head.next;
}
else
{
Node current = head;
for(int i = 0;i<idx-1;i++)
current = current.next;
current.next = current.next.next;
}
}
전체 코드
public class LinkedList {
// 마직막 블록과 이르려면 마지막블록을 찾아야함
// 그러기위해선 첫 번쨰 놈을 알아야함
// 실제 데이터를 저장할 공간하고 그 데이터 공간을 서로 연결할 고리를 만들어보겠습니다.
// 최초의 노드, 시작점 구현
private Node head = null;
public void insert(int data)
{
// 새로운 노드를 인스턴스로 만듦
Node newBlock = new Node();
// 인스턴트 안의 변수 선언(노드 값)
newBlock.data = data;
//
if(head == null)
{
head = newBlock;
return;
}
//head 부터 시작
Node current = head;
// current가 곧 head
// 노드의 next가 비어있지 않으면 계속 다음 블럭으로 가서 next를 확인한다
while(current.next != null)
{
current = current.next;
}
// 마지막이면 while문 빠져나와 그 next에 주소를 붙인다.(연결한다)
current.next = newBlock;
}
// 출력함수
public void print()
{
Node current = head;
while(current != null)
{
System.out.println(current.data);
current = current.next;
}
}
// 특정 값 출력
public int getData(int idx)
{
Node current = head;
for(int i = 0;i<idx;i++)
current = current.next;
return current.data;
}
//head값 바꾸기
public void insertHead(int data)
{
Node newBlock = new Node();
newBlock.data = data;
newBlock.next = head;
head = newBlock;
}
public int getLastData()
{
Node current = head;
while(current.next != null)
current = current.next;
return current.data;
}
// 맨 마지막 값 지우기
public void deleteLast()
{
if(head == null)
return;
Node current = head;
//if(head.next == null)
// head 하나만 현재 LinkedList에 있을 경우도 특별한 처리가 필요합니다. 그런데 엄청 쉬워요
while(current.next.next != null)
current = current.next;
current.next = null;
}
public void deleteAt(int idx)
{
// 헤드가 널이면 지우면 안돼
if(head == null)
return;
// 헤드를 지워버리는 방법
else if(idx == 0)
{
// head 를 지울꺼에요.
// 두번째 블럭이 헤드가 되면 된다
// 원래는 첫번 쨰 블럭이 헤드
head = head.next;
}
else
{
Node current = head;
for(int i = 0;i<idx-1;i++)
current = current.next;
current.next = current.next.next;
}
}
//노드 사이에 넣기
public void insertAt(int idx, int data)
{
Node newBlock = new Node();
newBlock.data = data;
// 추가할 위치까지 간다
Node current = head;
for(int i = 0;i<idx;i++)
current = current.next;
Node temp = current.next;
current.next = newBlock;
newBlock.next = temp;
}
}