코딩테스트-2 차에는 LinkedList에 대해서 코드로 구현해 보겠다.
구현 방식은 위에 있는 작업 방식대로 SingleLinkedList와 DoubleLinkedList로 나뉘어서 만들어보겠다.
싱글 링크드 리스트(단순 연결 리스트) 데이터 구조는 노드를 기준으로 여러 개의 노드를 순서대로 연결하여 저장한다.
각각의 노드들은 Head Node를 시작으로 Data와 다음 노드를 연결하는 주소값이 저장되어 있다.
밑에 있는 코드는
- 노드 생성
- 싱글 링크드 리스트 생성
- 싱글 링크드 리스트 데이터 추가(No 삽입)
public class Node<T> {
T data; //T 제내릭 타입으로 모든 형태의 데이터를 받을 수 있게 했다.
Node next; //노드는 데이터와 주소값으로 저장되어 있고 그 주소값은 다음 노드를 가르키는
//포인트형식이기에 자바에는 포인트 형식이 없으므로 다음 노드값을 넣었다.
Node(T data){
this.data = data; //노드를 생성시 헤더의 데이터를 넣고 생성한다.
this.next = null; //그 다음 노드는 생성시 null을 기준으로 생성된다.
}
}
- 노드 생성
public class SingleLinkedList<T> {
//싱글 링크드 리스트 클래스에 내부 클래스로 노드 클래스를 넣는다.
public class Node<T>{
T data;
Node next;
public Node(T data){
this.data = data;
this.next = null;
}
}
// 싱글 링크드 리스트에 각 사용할 객체를 정의한다.
public Node<T> head = null;
public Node<T> tail = null;
//데이터 삽입 메서드를 정의하자
public void addNode(T data){
//새 노드를 생성하자
Node<T> newNode = new Node(data);
// 리스트의 헤드가 null 값인지를 확인한다. 노드의 첫 생성인지 아님 생성된 노드에 데이터를
// 넣는지 확인하는 작업이다.
if(head == null){
// 리스트 헤드가 empty면 head와 tail 둘다 새로운 노드를 가르킨다.
head = newNode;
tail = newNode;
}
else{
// 리스트 head가 null이 아니라면 즉 데이터가 있다면
// newNode는 tail의 다음 값을 가르키는 곳으로 더해질것이다.
tail.next = newNode;
// newNode는 리스트의 꼬리가 될것이다.
tail = newNode;
}
}
public void display(){
// 현재 위치는 head로 향한다
Node current = head;
if(head == null){
System.out.println("List가 비어있다");
return;
}
System.out.println("싱글 링크드 리스트 :");
while(current != null){
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
//제너릭을 Integer로 정의해서 싱글링크드 리스트를 생성한다.
SingleLinkedList<Integer> sList = new SingleLinkedList<>();
//클래스에 데이터를 넣어준다.
sList.addNode(1);
sList.addNode(2);
sList.addNode(3);
//출력한다.
sList.display();
}
}
2) 싱글 링크드 리스트 생성
3) 싱글 링크드 리스트 데이터 추가(No 삽입)
싱글 링크드 리스트
다음 코드는
1)싱글 링크드 리스트 조회
public class SingleLinkedListTest2<T> {
public class Node<T>{
T data;
Node<T> next;
public Node(T data){
this.data = data;
}
}
public Node<T> head = null;
public Node<T> tail = null;
public void addNode(T data){
Node<T> newNode = new Node(data);
if(head == null){
head = newNode;
tail = newNode;
}else{
tail.next = newNode;
tail = newNode;
}
}
// addNode와 Node클래스는 앞 코드와 비슷하다.
//노드를 조회하는 메서드이다.
public void searchNode(T data){
// 위치 변수 i이다
int i = 1;
// 조회할 데이터 존재 유무 판별 변수이다.
boolean flag = false;
// 현재 노드는 헤더로 시작한다.
Node<T> current = head;
// 해더가 null일 경우 리스트가 비었다는 데이터를 출력하고 메서드를 종료시킨다.
if(head == null){
System.out.println("list는 빈값이다.");
return;
// 헤더가 데이터가 있는 경우이다.
}else{
// 현재 데이터가 없을 때까지 반복문을 돌린다.
while(current != null){
// 현재 데이터가 조회하려는 데이터와 일치하는 경우에는 flag를 true로 반환한다.
if(current.data == data){
flag = true;
}
//데이터 조회시 다음 노드값을 현재 노드에 대입하고 위치값도 1을 더한다.
//while 반복문에 따라 데이터가 존재 하지 않으면 그대로 반복문은 종료되고 데이터가 없을 경우 계속해서 다음
//노드값을 조회하게 된다.
current = current.next;
i++;
}
}
//앞에 데이터 조회 유무 flag가 true인 경우는 위치를 출력시키고
//flag가 false인 경우는 조회하려는 데이터가 없음을 출력한다.
if(flag)
System.out.println("조회 하려는"+data+" 의 위치 : "+i);
else
System.out.println("조회 하려는"+data+" 는 리스트에 존재하지 않는다.");
}
public static void main(String[] args) {
SingleLinkedListTest2 sList = new SingleLinkedListTest2();
sList.searchNode(0);
sList.addNode(1);
sList.addNode(2);
sList.searchNode(0);
sList.searchNode(2);
}
}
- 데이터 삽입
public class SingleLinkedListInsertMiddle<T> {
public class Node<T>{
T data;
Node next;
public Node(T data) {
this.data = data;
this.next = null;
}
}
//전체 길이 사이즈이면서 위치를 찾기위한 변수이다.
public int size;
public Node<T> head = null;
public Node<T> tail = null;
public void addNode(T data){
Node<T> newNode = new Node(data);
if(head == null){
head = newNode;
tail = newNode;
}else{
tail.next = newNode;
tail = newNode;
}
//해당 노드들의 연결 전체 사이즈 이다.
size++;
}
public void insertNodeInMiddle(T data){
Node<T> newNode = new Node(data);
if(head == null){
head = newNode;
tail = newNode;
}
else{
//temp는 임시 데이터 저장 노드다. current는 head를 기준으로 count 갯수에 따라 이동하는 값이다.
Node temp, current;
int count = (size % 2 == 0)?(size/2):((size+1)/2);
temp =head;
current = null;
for(int i = 0; i<count ; i++){
current = temp;
// temp는 무조건 current 다음 데이터 값을 가진다.
temp = temp.next;
}
// 현재 위치의 값의 다음 노드는 insert하려는 data 노드를 넣어준다.
current.next = newNode;
// 현재 current newNode temp 순으로 데이터가 정렬된다.
newNode.next = temp;
}
size++;
}
public void display(){
Node current = head;
if(head == null){
System.out.println("List is empty");
return;
}
while(current != null){
System.out.print(current.data+" ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
SingleLinkedListInsertMiddle<Integer> slm = new SingleLinkedListInsertMiddle();
slm.addNode(1);
slm.addNode(2);
slm.addNode(3);
slm.addNode(4);
slm.display();
slm.insertNodeInMiddle(6);
slm.display();
}
}
