package 数据结构算法.链表;
/*
*定义节点
* 链表由节点构成
*/
public class Node<E> {
private E e; //数据data
private Node<E> next; //指向下一个节点
public Node() {
}
public Node(E e) {
this.e = e;
}
public Node<E> getNext() {
return next;
}
public void setNext(Node<E> next) {
this.next = next;
}
public E getE() {
return e;
}
public void setE(E e) {
this.e = e;
}
}
package 数据结构算法.链表;
/*
* 定义实现类MyLinkedList
* 实现链表的基本功能:增删改查
*/
public class MyLinkedList<E> {
//声明头节点尾节点
private Node<E> head;
private Node<E> last;
//链表的大小
private int size;
private int modcount; //计算被修改的次数
public MyLinkedList() {
head = new Node<E>();//实例化头结点
last = head;
}
/*
*返回单链表中存储的元素总数
*/
public int size() {
return size;
}
/*
*获取指定索引位置的节点对象
*/
public Node<E> get(int index) {
if (index < 0 || index > size - 1)
return null;
Node<E> node = head.getNext();//将头结点的下一个节点赋给Node
for (int i = 0; i < index; i++) {
node = node.getNext();//获取node的下一个节点
}
return node;
}
/*
*获取指定索引位置的数据
*/
public E getValue(int index) {
if (index < 0 || index > size - 1)
return null;
Node<E> node = get(index);
return node.getE();
}
/*
*增加元素
*/
public void add(E e) {
Node<E> node = new Node<E>(e); //以e实例化一个节点
last.setNext(node);//往尾节点后追加节点
last = node;//该节点设为最后一个节点
size++;
modcount++;
}
/*
*指定位置插入元素,返回插入的节点数据
*/
public E add(int index, E e) {
if (index < 0 || index > size - 1)
return null;
Node<E> node = new Node<E>(e); //实例化一个节点
//找到插入的原节点
Node<E> oldNode = get(index);
if (index == 0) {//当索引为0时
head.setNext(node);
} else {
//找到插入节点的上一个
Node<E> bNode = get(index - 1);
bNode.setNext(node);
}
node.setNext(oldNode);
size++;
modcount++;
return oldNode.getE();
}
/*
*删除指定的节点e,并返回删除节点的数据
*/
public E delete(int index) {
if (index < 0 || index > size - 1)
return null;
if (index == 0) {//当索引为1,令头结点的下一个节点为头结点
Node<E> node = head.getNext();
head.setNext(node.getNext());
}
//获取要删除节点的前一个节点
Node<E> bNode = get(index - 1);
//获取要删除的节点
Node<E> Node = bNode.getNext();
//获取要删除节点的下一个节点
Node<E> nNode = Node.getNext();
//删除该节点
bNode.setNext(nNode);
//清除Node的下一个节点
Node.setNext(null);
size--;
modcount++;
return Node.getE();//返回节点中的数据域
}
/*
*修改指定位置的数据域并返回修改后的数据
*/
public E set(int index, E e) {
if (index < 0 || index > size - 1)
return null;
//获取指定位置的原节点
Node<E> node = get(index);
node.setE(e);
modcount++;
return node.getE();
}
}
package 数据结构算法.链表;
/*
*定义测试类
*/
public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedList<String> list = new MyLinkedList<>();
//测试add
list.add("one");
list.add("two");
list.add("three");
list.add("four");
list.add(0,"newone");
list.add(1,"newtwo");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.getValue(i)+" ");
}
//测试set
System.out.println();
list.set(0, "111");
list.set(1, "222");
System.out.println(list.getValue(0) + " " + list.getValue(1));
//测试delete
System.out.println();
list.delete(1);
for (int i = 0; i < list.size(); i++) {
System.out.print(list.getValue(i)+" ");
}
}
}
运行结果如下:
以上就是全部知识点内容,感谢大家对天达云的支持。