코딩테스트-2 차에는 LinkedList에 대해서 코드로 구현해 보겠다.
![](https://blog.kakaocdn.net/dn/RYMEq/btrP6io7kph/QoZQk3rPXivjzMigKLUkhK/img.png)
구현 방식은 위에 있는 작업 방식대로 SingleLinkedList와 DoubleLinkedList로 나뉘어서 만들어보겠다.
![](https://blog.kakaocdn.net/dn/WSKXQ/btrP3MSvxyc/KV9jc2fvSy8GGWpDlWBYY0/img.png)
싱글 링크드 리스트(단순 연결 리스트) 데이터 구조는 노드를 기준으로 여러 개의 노드를 순서대로 연결하여 저장한다.
각각의 노드들은 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); } }
- 데이터 삽입
![](https://blog.kakaocdn.net/dn/c2jiAi/btrP9Gjj4Xt/Bk5a3GZ81aGOiCXwE5yaK1/img.png)
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(); } }