연결리스트(Linked List)
데이터를 링크로 연결해서 관리하는 자료구조
자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음
장단점
데이터 공간을 미리 할당할 필요가 없음
-> 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이(구현 X, 메모리 관리 측면에서)
위와 같이 배열의 경우에는 하나의 데이터를 삭제하거나, 추가 하는 경우 작업 진행 이후 모든 데이터들이 재배치 되어야 함
반면 연결리스트의 경우 데이터가 삭제 되거나 추가되면 해당 노드를 가리키는 포인터만 변경해주기 때문에 배열보다 삭제나 추가에서 효율적
-> 삭제나 추가가 O(1)에 가능
하지만 연결구조를 위한 별도 데이터 공간(다음 데이터 링크 공간)이 필요하고,
연결 정보를 찾는 시간이 필요(접근 속도가 배열보다 상대적으로 느림)
배열의 경우에는 특정 데이터를 찾을때 인덱스가 있어 검색이 효율적인 반면, 연결 리스트는 정해진 위치를 알지 못하기 때문에 검색 시 데이터를 순회해 특정 데이터를 찾아야 함 : O(n)
데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요
기본구조
Node : 데이터 저장 단위로, 값과 포인터로 구성되어 있음
가장 첫번째 노드 : 헤더(헤드), 가장 마지막 노드 : 테일 이라고 부름
데이터 추가
-
가장 앞에 데이터를 추가하는 경우
추가할 데이터를 담을 노드를 생성 후, 링크 연결을 하고, head 이전 작업 -
가장 끝에 데이터를 추가하는 경우
추가할 데이터를 담을 노드 생성 후, head로 부터 끝 노드까지 순회하고 링크 연결 작업 -
중간에 추가하는 경우
추가할 데이터를 담을 노드를 생성하고, head로 부터 데이터 추가 위치 직전 노드까지 순회한 후 링크 연결 작업
데이터 삭제
맨 앞에 요소를 삭제할려면 삭제 대상 노드 지정(delete_node)후, head를 이전 하고 delete_node 삭제
맨 뒤에 요소 삭제시 head로 부터 가장 끝까지 순회한 후 끝 노드 삭제, 이후 삭제 이전 노드의 링크 처리
중간 요소 삭제 시 head로 부터 삭제 대상 노드까지 순회 및 해당 노드 지정(delete_node)
-> 이후 삭제 대상 이전/이후 노드의 링크 연결 작업 후 delete_node 삭제
추가/삭제에 나오는 delete_node 내용은 자바의 경우 GC가 있기에 코딩에 반영하지는 않음
삽입 삭제 구현 예시
class LinkedList2 extends LinkedList{
LinkedList2(Node node){
this.head = node;
}
// 연결 리스트에 데이터 추가
// before data가 null인 경우, 가장 뒤에 추가
// before_data에 값이 있는 경우, 해당 값을 가진 노드 앞에 추가
public void addData(int data, Integer beforeData){
if(this.head == null){
this.head = new Node(data, null);
return;
}else if(beforeData == null){
Node cur = this.head;
while(cur.next != null){
cur = cur.next;
}
cur.next = new Node(data, null);
}else{
Node cur = this.head;
Node prev = cur;
while(cur != null){
if(cur.data == beforeData){
if(cur == this.head){
this.head = new Node(data,this.head);
}else{
prev.next = new Node(data, cur);
}
break;
}
prev = cur;
cur = cur.next;
}
}
}
public void removeData(int data){
if(this.isEmpty()){
System.out.println("List is empty");
return;
}
Node cur = this.head;
Node prev = cur;
while(cur != null){
if(cur.data == data){
if(cur == this.head){
this.head = cur.next;
}else{
prev.next = cur.next;
}
break;
}
prev = cur;
cur = cur.next;
}
}
}양방향 연결 리스트(Doubly Linked List) 구현
// 양방향 연결리스트(Doubly Linked List) 구현
class NodeBi{
int data;
NodeBi next;
NodeBi prev;
NodeBi(int data, NodeBi next, NodeBi prev){
this.data = data;
this.next = next;
this.prev = prev;
}
}
class DoublyLinkedList extends LinkedList{
NodeBi head; NodeBi tail;
DoublyLinkedList(NodeBi node){
this.head = node;
this.tail = node;
}
public boolean isEmpty(){
if(this.head == null){
return true;
}
return false;
}
public void addData(int data, Integer beforeData){
if(this.head == null){
this.head = new NodeBi(data, null, null);
this.tail = this.head;
return;
}else if (beforeData == null){
this.tail.next = new NodeBi(data, null, this.tail);
this.tail = this.tail.next;
} else{
NodeBi cur = this.head;
NodeBi pre = cur;
while(cur != null){
if(cur.data == beforeData){
if(cur == this.head){
this.head = new NodeBi(data, this.head, null);
this.head.next.prev = this.head;
}else{
pre.next = new NodeBi(data, cur, pre);
cur.prev = pre.next;
}
break;
}
pre = cur;
cur = cur.next;
}
}
}
public void removeData(int data) {
if (this.isEmpty()) {
System.out.println("List is Empty!");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
while (cur != null) {
if (cur.data == data) {
if (cur == this.head && cur == this.tail) {
this.head = null;
this.tail = null;
} else if (cur == this.head) {
this.head = cur.next;
this.head.prev = null;
} else if (cur == this.tail) {
this.tail = cur.prev;
this.tail.next = null;
} else {
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}
}
public void showData(){
if(this.isEmpty()){
System.out.println("List is Empty!");
return;
}
NodeBi cur = this.head;
while(cur != null){
System.out.println(cur.data + " ");
cur = cur.next;
}
System.out.println();
}
public void showDataFromTail(){
if(this.isEmpty()){
System.out.println("List is Empty!");
return;
}
NodeBi cur = this.tail;
while(cur != null){
System.out.print(cur.data + " ");
cur = cur.prev;
}
System.out.println();
}
}이중 원형 연결 리스트(Circular Linked List) 구현
처음과 마지막 구분을 위해 더미 노드를 추가하기도 함
더미 노드는 연결 리스트의 시작점을 알리는 역할로, 맨 앞에 있는 노드
-> 아무런 값도 갖지 않는(None) 노드이며 연결 리스트가 비어 있는 상황에도 더미 노드가 1개 존재
class CircularLinkedList{
NodeBi head;
NodeBi tail;
CircularLinkedList(NodeBi node){
this.head = node;
this.tail = node;
node.next = this.head;
node.prev = this.tail;
}
public boolean isEmpty(){
if(this.head == null){
return true;
}
return false;
}
public void addData(int data, Integer beforeData){
if(this.head == null){
// 비어있을때 모두 다 자기 자신을 가리키는 노드를 추가
NodeBi newNodeBi = new NodeBi(data,null,null);
this.head = newNodeBi;
this.tail = newNodeBi;
newNodeBi.next = newNodeBi;
newNodeBi.prev = newNodeBi;
} else if(beforeData == null){
NodeBi newNodeBi = new NodeBi(data, this.head, this.tail);
this.tail.next = newNodeBi;
this.head.prev = newNodeBi;
this.tail = newNodeBi;
}else{
NodeBi cur = this.head;
NodeBi pre = cur;
do{
if(cur.data == beforeData){
if(cur == this.head){
NodeBi newNode = new NodeBi(data, this.head, this.tail);
this.tail.next = newNode;
this.head.prev = newNode;
this.head = newNode;
}else{
NodeBi newNode = new NodeBi(data, cur,pre);
pre.next = newNode;
cur.prev = newNode;
}
break;
}
pre = cur;
cur = cur.next;
}while(cur != this.head);
}
}
public void removeData(int data){
if(this.isEmpty()){
System.out.println("List is Empty!");
return;
}
NodeBi cur = this.head;
NodeBi pre = cur;
do{
if(cur.data == data){
if(cur == this.head && cur == this.tail){
this.head = null;
this.head = null;
}else if(cur == this.head){
cur.next.prev = this.head.prev;
this.head = cur.next;
this.tail.next = this.head;
}else if(cur == this.tail){
pre.next = this.tail.next;
this.tail = pre;
this.head.prev = this.tail;
}else{
pre.next = cur.next;
cur.next.prev = pre;
}
break;
}
pre = cur;
cur = cur.next;
}while(cur != head);
}
public void showData(){
if(this.isEmpty()){
System.out.println("List is Empty!");
return;
}
NodeBi cur = this.head;
while(cur.next != this.head){
System.out.print(cur.data + " ");
cur = cur.next;
}
System.out.println(cur.data);
}
}연습 문제
문제 1 : 중복 제거하기
public class Main {
public static LinkedList removeDup(LinkedList listBefore){
LinkedList listAfter = new LinkedList();
Node cur = listBefore.head;
while(cur != null){
if(listAfter.findData(cur.data) == false){
listAfter.addData(cur.data);
}
cur = cur.next;
}
return listAfter;
}
public static void main(String[] args) {
// 단방향 연결 리스트에서 중복 데이터를 찾아 삭제하기
// 입출력 예시)
// 입력 연결 리스트 : 1, 3, 3, 1, 4, 2, 4, 2
// 결과 연결 리스트 : 1, 3, 4, 2
LinkedList linkedList = new LinkedList();
linkedList.addData(1);linkedList.addData(3);linkedList.addData(3);
linkedList.addData(1);linkedList.addData(4);linkedList.addData(2);
linkedList.addData(4);linkedList.addData(2);
linkedList.showData(); // 1 3 3 1 4 2 4 2
linkedList = removeDup(linkedList);
linkedList.showData(); // 1 3 4 2
}
}문제 2 : Palindrome
// 입력 예시)
// 입력 연결 리스트 : 1,3,5,3,1 -> true
// 3,5,5,3 -> true 1,3,5,1 -> false
public class Practice4 {
public static boolean checkPalindrome(LinkedList list) {
Node cur = list.head;
Node left = list.head;
Node right = null;
int cnt = 0;
while(cur != null){
cnt++;
right = cur;
cur = cur.next;
}
for(int i = 0; i < cnt / 2; i++){
Node prevRight = right;
if (left.data != right.data){
return false;
}
if(left.next != right){
left = left.next;
}
right = left;
while(right.next != prevRight){
right = right.next;
}
}
return true;
}
}
// 내 코드
public static boolean checkPanlindrome(LinkedList list){
Node front = list.head;
while(true){
Node back = list.head;
Node pre = back;
while(back.next != null){
pre = back;
back = back.next;
}
if(!(front.data == back.data)){
return false;
}else if(front == back || front.next == back){
return true;
}
front = front.next;
pre.next = null;
}
}문제 3.연결리스트 부분 뒤집기
package org.example;
// 연결리스트 부분 뒤집기
// 주어진 연결 리스트에서 시작 위치부터 끝 위치 사이의 노드들을 뒤집으시오.
// 입력 예시)
// 입력 연결 리스트 : 1,2,3,4,5 시작위치 : 2 끝 위치 : 4
// 처음 위치는 1부터라고 가정
// 결과 연결 리스트 1,4,3,2,5
public class Practice4 {
public static LinkedList reverseList(LinkedList list, int left, int right) {
Node cur1 = null;
Node pre1 = null;
cur1 = list.head;
for(int i = 0; i < left - 1; i++){
pre1 = cur1;
cur1 = cur1.next;
}
Node cur2 = cur1;
Node pre2 = pre1;
Node after = null;
for(int i = left; i <= right; i++){
after = cur2.next;
cur2.next = pre2;
pre2 = cur2;
cur2 = after;
}
pre1.next = pre2;
cur1.next = cur2;
return list;
}
public static void main(String[] args){
LinkedList linkedList = new LinkedList();
linkedList.addData(1);linkedList.addData(2);linkedList.addData(3);
linkedList.addData(4);linkedList.addData(5);
linkedList.showData();
linkedList = reverseList(linkedList,2,4);
}
}문제4. 연결 리스트 배열 사용 연습
// Practice4
// 연결 리스트 배열 사용 연습
// 주어진 문자열 배열을 연결 리스트 배열로 관리하는 코드를 작성하시오.
// 관리 규칙은 다음과 같다 -> 각 문자열의 첫 글자가 같은 것끼리 같은 연결 리스트로 관리하기
public static void dataCollect(String[] data) {
HashSet<Character> set = new HashSet<>();
for(String item: data){
set.add(item.charAt(0));
}
System.out.println(set);
Character[] arr = set.toArray(new Character[0]);
LinkedList[] linkedList = new LinkedList[set.size()]; //linkedList[0].~~~ 이런식으로 접근 불가
for (int i = 0; i < linkedList.length; i++) {
linkedList[i] = new LinkedList(null, arr[i]);
}
for(String item : data){
for(LinkedList list : linkedList){
if(list.alphabet == item.charAt(0)){
list.addData(item);
}
}
}
for(LinkedList list : linkedList){
System.out.print(list.alphabet + " : ");
list.showData();
}
}
public static void main(String[] args) {
// Test code
String[] input = {"apple", "watermelon", "banana", "apricot", "kiwi", "blueberry", "cherry", "orange"};
dataCollect(input);
System.out.println();
String[] input2 = {"ant", "kangaroo", "dog", "cat", "alligator", "duck", "crab", "kitten", "anaconda", "chicken"};
dataCollect(input2);
}
Journey for Backend Developer