测试类
package test;
public class TestLinkedList {
public static void main(String[] args) {
LinkedList list = new LinkedList();
//在双链表尾部添加节点
list.addLast("cab");
list.addLast("bba");
list.addLast("bab");
list.addLast("abb");
list.addLast("bab");
//在双链表头部添加节点
list.addFirst("aaa");
System.out.println("--------------排序----------------");
//调用插入排序方法
list.insertSort();
//调用遍历函数
list.travers();
}
}
下面是插入排序的方法
public void insertSort() {
Node curr = first.next;//开始时从第二个节点开始往前看
while(curr != null) {
Node prev = curr.prev;
while(prev != null) {
if (curr.data.compareTo(prev.data) < 0) {//如果当前节点小于前一个节点就继续往前查看
prev = prev.prev;
} else break;
}
//因为在之后会改变当前节点的位置，所以先定义临时变量记录改变前的节点位置
Node cNext = curr.next;
if (prev == null) {//如果找到的插入位置为头部直接删除节点后调用头插法
String val = curr.data;
unlink(curr);
addFirst(val);
} else {
//此部分逻辑完成把当前节点的前驱后后继关联上
//然后把当前节点插入到应该存在的位置，也就是prev之后。
curr.prev.next = curr.next;
if (curr.next != null) {
curr.next.prev = curr.prev;
}
curr.next = prev.next;
prev.next.prev = curr;
prev.next = curr;
curr.prev = prev;
}
curr = cNext;
}
}
方法类调式的时候使用这个
/*双链表测试类*/
public class TestLinkedList {
public static void main(String[] args) {
//要访问双链表中的方法，就需要使用new关键字创建该双链表的对象。
LinkedList list = new LinkedList();
//String str = new String("abc");
//调用list的添加方法
list.add("dcd");
list.add("bbc");
list.add("fgh");
list.add("bbc");
list.add("abc");
//调用遍历方法
//list.traverse();
//list.addFirst("world");
//list.remove(-2);
//list.insert(4, "world");
list.traverse();
list.insertSort();
list.traverse();
}
}
/*
实现双链表
该类里的属性和方法都没有用关键字static修饰
所以访问这些属性和方法的时候都要使用对象的引用取访问
*/
class LinkedList {
//头节点
Node first = null;
//尾节点
Node last = null;
//记录节点个数
int size = 0;
/*定义添加元素的方法*/
public void add(String val) {
addLast(val);
}
/*尾插法*/
public void addLast(String val) {
//要把val添加到链表中，需要做什么？
//第一步：创建节点，
Node newNode = new Node();
//第二步：把值val存入节点的数据区域
newNode.data = val;
//首次添加节点时，头节点和尾节点都是null.
if(last == null) {
//首次添加需要把头节点和尾节点的引用都移动到指向第一个节点
first = newNode;
last = newNode;
} else {//非首次插入节点
last.next = newNode;//让链表的末节点的next域指向新创建的节点
newNode.prev = last;//让新创建节点的prev域指向链表的末节点
last = newNode;//最后把last移动到指向新创建的节点
}
size++;
}
/*头插法*/
public void addFirst(String val) {
//要把val添加到链表中，需要做什么？
//第一步：创建节点，
Node newNode = new Node();
//第二步：把值val存入节点的数据区域
newNode.data = val;
//首次插入值头和尾节点都是null
if(first == null) {
first = newNode;
last = newNode;
} else {
newNode.next = first;
first.prev = newNode;
first = newNode;
}
size++;
}
/*检查位置边界*/
public void checkBoundary(int position) {
if (position < 0 || position > size)
throw new RuntimeException("下标过了啊。。。。。。");
}
/*该方法根据指定位置返回节点*/
public Node node(int position) {
//定义临时遍历记录头节点
Node x = first;
//查找position位置处的节点
for (int i = 1; i < position; i++) {
x = x.next;
}
return x;
}
/*解除节点的关系*/
public Node unlink(Node x){
//定义变量记录需要删除的节点
Node item = x;
//记录当前节点的next;
Node next = x.next;
//记录当前节点的prev
Node prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//x.data = null;
size--;
return item;
}
/*删除节点*/
public Node remove(int position) {
//位置检查
checkBoundary(position);
//调用方法根据位置查找节点
Node node = node(position);
//解除引用并返回
return unlink(node);
}
/*把指定节点的数据域更新为指定的值*/
public void update(int position, String value) {
//检查边界
checkBoundary(position);
//查找需要更新的节点并设置新的值
node(position).data = value;
}
/*获取指定节点的值*/
public String get(int position) {
return node(position).data;
}
/*指定位置插入一个节点*/
public void insert(int position, String value) {
//单独处理插链表尾部
if((size + 1) == position) {
addLast(value);
return;
}
//单独处理插入链表头部
if (position == 1) {
addFirst(value);
return;
}
//查找到需要插入节点的位置
Node node = node(position);
//获取当前节点的前一个节点
Node prevNode = node.prev;
//创建节点
Node newNode = createNode(value);
prevNode.next = newNode;
newNode.prev = prevNode;
newNode.next = node;
node.prev = newNode;
size++;
}
/*创建节点*/
public Node createNode(String val) {
Node node = new Node();
node.data = val;
return node;
}
/*去除重复节点*/
public void distinct() {
Node one = first;
int outSize = 1;
while(one != null) {
Node two = one.next;
int count = outSize + 1;
while(two != null) {
if (one.data == two.data) {
two = two.next;
remove(count);
} else {
two = two.next;
count++;
}
}
outSize++;
one = one.next;
}
}
public void insertSort() {
Node curr = first.next;//开始时从第二个节点开始往前看
while(curr != null) {
Node prev = curr.prev;
while(prev != null) {
if (curr.data.compareTo(prev.data) < 0) {//如果当前节点小于前一个节点就继续往前查看
prev = prev.prev;
} else break;
}
//因为在之后会改变当前节点的位置，所以先定义临时变量记录改变前的节点位置
Node cNext = curr.next;
if (prev == null) {//如果找到的插入位置为头部直接删除节点后调用头插法
String val = curr.data;
unlink(curr);
addFirst(val);
} else {
//此部分逻辑完成把当前节点的前驱后后继关联上
//然后把当前节点插入到应该存在的位置，也就是prev之后。
curr.prev.next = curr.next;
if (curr.next != null) {
curr.next.prev = curr.prev;
}
curr.next = prev.next;
prev.next.prev = curr;
prev.next = curr;
curr.prev = prev;
}
curr = cNext;
}
}
/*遍历链表*/
public void traverse() {
Node temp = first;
while(temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
}
class Node {
//数据域
String data;
//前驱引用
Node prev;
//后继引用
Node next;
}
评论 (0)