/**
* 单向链表实现类
* @Description
* 类描述:
* @author GaoAnQiu
* @Date
* @modify
* 修改记录:
*
*/
public class Link {
private int size = 0;
private Node first;
private Node last;
public Node getFirst() {
return first;
}
public void setFirst(Node first) {
this.first = first;
}
public Node getLast() {
return last;
}
public void setLast(Node last) {
this.last = last;
}
public Link() {
}
/**
* 返回链表长度
* @Description
* 方法描述:
* @return 返回类型: int
* @return
*/
public int getLength() {
return size;
}
public void printLink(Link link) {
Node temp = first;
while (temp != null) {
System.out.print(temp.getData() + "-->");
temp = temp.getNext();
}
System.out.println();
}
/**
* 返回指定位置的节点
* @Description
* 方法描述:
* @return 返回类型: Node
* @param index
* @return
*/
public Node get(int index) {
Node temp = first;
for (int i = 0; i < index; i++) {
temp = temp.getNext();
}
return temp;
}
/**
* 插入第一个元素,头和尾都指向同一个元素
* @Description
* 方法描述:
* @return 返回类型: void
*/
private void onetNode(int element) {
first = new Node();
first.setData(element);
last = first;
}
public void addHead(int element) {
if (size == 0) {
onetNode(element);
} else {
Node node = new Node();
node.setData(element);
node.setNext(first);
first = node;
}
size++;
}
/**
* 插入尾结点
* @Description
* 方法描述:
* @return 返回类型: void
* @param element
*/
public void addTail(int element) {
if (size == 0) {
onetNode(element);
} else {
Node node = new Node();
node.setData(element);
last.setNext(node);
last = node; //将插入的结点设置为尾结点
size++;
}
}
/**
* 插入中间元素
* 头尾两处需要特殊处理
* @Description
* 方法描述:
* @return 返回类型: void
* @param index
* @param element
*/
public void add(int index, int element) {
if (index > size) {
throw new IndexOutOfBoundsException("待插入的位置超过链表的最大长度。");
} else {
if (index == 0) {
//下标为0时,插入头元素
addHead(element);
} else if (size == index) {
//下标与链表长度一致时,插入尾元素
addTail(element);
} else {
Node preNode = get(index - 1); //
Node nextNode = get(index);
Node newNode = new Node();
newNode.setData(element);
preNode.setNext(newNode);
newNode.setNext(nextNode);
size++;
}
}
}
/**
* 删除头节点
* @Description
* 方法描述:
* @return 返回类型: void
*/
public void delHead() {
if (size == 0) {
throw new IndexOutOfBoundsException("空链表,无元素可删除");
} else {
if (size == 1) {
//只有一个节点时,清空链表
clear();
} else {
Node nextNode = first.getNext();
first = nextNode;
}
size--;
}
}
/**
* 清空链表
* @Description
* 方法描述:
* @return 返回类型: void
*/
public void clear() {
first = last = null;
size = 0;
}
public void delTail() {
if (size == 0) {
throw new IndexOutOfBoundsException("空链表,无可删除的元素。");
} else if (size == 1) {
clear();
} else {
//取出尾节点的前一个节点,next赋值为null
Node preTail = get(size - 2);
preTail.setNext(null);
last = preTail;
size--;
}
}
/**
* 删除节点
* @Description
* 方法描述:
* @return 返回类型: void
* @param index
*/
public void del(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException("删除位置越界");
} else {
if (index == 0) {
delHead();
} else if (index == size - 1) {
delTail();
} else {
Node preNode = get(index - 1);
Node nextNode = get(index + 1);
preNode.setNext(nextNode);
size--;
}
}
}
}
public class Node {
private int data;//数据
private Node next;//指针
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}