一、链表
1、如何实现单链表的增删操作?
/**
*结点的定义
*/
class Node{
Node next = null;
int data;
public Node(int data){
this.data = data;
}
}
单链表的插入操作是将值为x的新结点插入到单链表的第i个结点的位置上,即插入到数据元素ai-1与ai之间。具体步骤如下: 1)找到ai-1的引用(存储位置)p;
2)生成一个数据域为x的新结点s;
3)设置p.next = s;
4)设置s.next = ai;
单链表的删除操作是将单链表的第i个结点删去。具体步骤如下:
1)找到ai-1的存储位置p;
2)令p.next指向ai的直接后继结点ai+1;
链表的基本操作如下:
public class MyLinkedList{ Node head = null; //链表头的引用 /** *向链表中插入数据 */ public void addNode(int d){ Node newNode = new Node(d); if(head == null){ head = newNode; return; } Node temp = head; //辅助指针 while(temp.next != null){ temp = temp.next; } //末尾增加结点 temp.next = newNode; } /** *删除第index个结点 */ public Boolean deleteNode(int index){ if(index < 1 || index > length){ return false; } //删除链表第一个元素 if(index == 1){ head = head.next; return true; } int i = 2; Node preNode = head; //辅助指针 Node curNode = preNode.next; //如果第二个结点存在 while(curNode != null){ if(i == index){ preNode.next = curNode.next; return true; } preNode = curNode; curNode = curNode.next; i ++; } return true; } /** *返回结点的长度 */ public int length(){ int length = 0; Node temp = head; while(temp.next != null){ length ++; temp = temp.next; } return length; } /** *对链表进行排序,返回排序后的头结点 */ public Node orderList(){ Node nextNode = null; int temp = 0; Node curNode = head; //辅助指针 while(curNode.next != null){ nextNode = curNode.next; while(nextNode != null){ if(curNode.data > nextNode.data){ //交换数据 temp = curNode.data; curNode.data = nextNode.data; nextNode.data = temp; } nextNode = nextNode.next; } curNode = curNode.next; } return head; } /** *打印链表 */ public void printList(){ Node temp = head; while(temp.next != null){ System.out.println(temp.data + "->"); temp = temp.next; } } }