java实现单链表增删改查的实例代码详解

更新时间：2020-09-09 10:24:01 作者：startmvc

package数据结构算法.链表;/**定义节点*链表由节点构成*/publicclassNode<E>{privateEe;//数据datap


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)+" ");
 }
 }
}

运行结果如下：