java数据结构--单链表
单链表
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
单向链表（Single-Linked List）
单链表是链表中结构最简单的。一个单链表的节点(Node)分为两个部分，第一个部分(data)保存或者显示关于节点的信息，另一个部分存储下一个节点的地址。最后一个节点存储地址的部分指向空值。
单向链表其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。由于不需要按顺序存储，链表在插入、删除数据元素时比顺序存储要快，但是在查找一个节点时则要比顺序存储要慢
使用链式存储可以克服顺序线性表需要预先知道数据大小的缺点，链表结构可以充分利用内存空间，实现灵活的内存动态管理。但是链式存储失去了数组随机存取的特点，同时增加了节点的指针域，空间开销较大。
单向链表只可向一个方向遍历，一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。而插入一个节点，对于单向链表，我们只提供在链表头插入，只需要将当前插入的节点设置为头节点，next指向原头节点即可。删除一个节点，我们将该节点的上一个节点的next指向该节点的下一个节点。
不过在下面实现了在指定位置添加删除节点
public class Node {
public int data;
/**
* 数据域
*/
public Node next;
public Node(int data) {
this.data = data;
}
public Node() {
}
/**
* 指针域
*/
/**
* @Author liuhaidong
* @Description 显示此方法
* @param
* @Date 9:40 2019/10/11 0011
*/
public void display(){
System.out.println(data + " ");
}
}
public class SingleLinkedList {
private Node head;
//头节点
private int size;
//链表节点个数
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public SingleLinkedList(){
size = 0;
head = null;
}
/**
* @Author liuhaidong
* @Description 在链表头部插入元素(已测试)
* @param
* @Date 9:47 2019/10/11 0011
*/
public void addFirstNode(int data){
Node newHead = new Node(data);
if(size == 0){
head = newHead;
}else {
newHead.next = head;
head = newHead;
}
size ++;
}
/**
* @Author liuhaidong
* @Description 在指定位置插入节点(已测试)
* @param
* @Date 11:04 2019/10/11 0011
*/
public void addNode(int position,int data) {
if(size ==0){
addFirstNode(data);
//如果此时没有元素
}
if (position > size + 1) {
System.out.println("the position is too large");
} else {
int index = 1;
for (Node x = head; x != null; x = x.next) {
if (index + 1 == position) {
Node temp = new Node(data);
temp.next = x.next;
//这一步相当于把原来的接到我现在加上去的下一个
x.next = temp;
//然后再接上去
size++;
break;
}
index++;
}
}
}
/**
* @Author liuhaidong
* @Description 删除一个头结点(已测试)
* @param
* @Date 9:48 2019/10/11 0011
*/
public void deleteFirstNode(){
Node tempNode = head;
head = tempNode.next;
size --;
}
/**
* @Author liuhaidong
* @Description 查找指定元素(已测试)
* @param
* @Date 9:54 2019/10/11 0011
*/
public boolean find(int data){
if(size == 0){
return false;
}
Node temp = head;
for (int i = 0; i <size ; i++) {
if(data == temp.data){
return true;
}else {
temp = temp.next;
}
}
return false;
}
/**
* @Author liuhaidong
* @Description 查找正数第k个元素(已测试)
* @param
* @Date 10:01 2019/10/11 0011
*/
public Node findNde(int k){
if(k<1 || k>size){
//不合法的k
return null;
}
Node temp = head;
for (int i = 0; i <k-1 ; i++) {
temp = temp.next;
}
return temp;
}
/**
* @Author liuhaidong
* @Description 判断链表是否为空(已测试)
* @param
* @Date 10:27 2019/10/11 0011
*/
public boolean isEmpty(){
return (size == 0);
}
/**
* @Author liuhaidong
* @Description 删除指定的元素，删除成功返回true(已测试)
* @param
* @Date 10:29 2019/10/11 0011
*/
public boolean deleteByData(int data){
if(size == 0){
return false;
}
Node current = head;
Node previous = head;
while (current.data != data) {
if (current.next == null) {
return false;
} else {
previous = current;
current = current.next;
}
}
//如果删除的节点是第一个节点
if (current == head) {
head = current.next;
size--;
} else {//删除的节点不是第一个节点
previous.next = current.next;
size--;
}
return true;
}
/**
* @Author liuhaidong
* @Description 删除任意位置的节点(已测试)
* @param
* @Date 10:30 2019/10/11 0011
*/
public void deleteByIndex(int position){
if(size == 0){
System.out.println("链表为空");
}
if (position > size){
System.out.println("the position is too large");
}else {
int index = 1;
// 记录遍历的位置
for (Node x = head; x != null; x = x.next) {
if (index + 1 == position) {
x.next = x.next.next;
size--;
break;
}
index++;
}
}
}
/**
* @Author liuhaidong
* @Description 显示出所有的节点信息(已测试)
* @param
* @Date 10:55 2019/10/11 0011
*/
public void displayAllNode(){
if(size > 0){
Node node = head;
int tempSize = size;
if(tempSize == 1){
//当前链表只有一个节点
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0){
if(node.equals(head)){
System.out.print("["+node.data+"->");
}else if(node.next == null){
System.out.print(node.data+"]");
}else {
System.out.print(node.data + "->");
}
node = node.next;
tempSize--;
}
}
}
}
主函数
public class Main {
public static void main(String[] args) {
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addNode(1,1);
linkedList.displayAllNode();
System.out.println();
linkedList.addNode(2,2);
linkedList.displayAllNode();
System.out.println();
linkedList.addNode(2,3);
linkedList.displayAllNode();
System.out.println();
System.out.println(linkedList.getSize());
// linkedList.addFirstNode(120);
// linkedList.addFirstNode(1);
// linkedList.addFirstNode(3);
// linkedList.displayAllNode();
// System.out.println();
// System.out.println(linkedList.find(1));
// System.out.println(linkedList.findNde(1).data);
// System.out.println(linkedList.isEmpty());
// linkedList.deleteByIndex(2);
// linkedList.displayAllNode();
// System.out.println();
// linkedList.deleteByData(3);
// linkedList.displayAllNode();
// System.out.println();
// linkedList.deleteFirstNode();
// linkedList.displayAllNode();
// System.out.println();
// System.out.println("****************************");
// System.out.println(linkedList.getSize());
// linkedList.addNode(1,2);
// linkedList.displayAllNode();
// System.out.println();
}
}
链表实现栈
public class MyStack {
/** Initialize your data structure here. */
private SingleLinkedList link;
public MyStack() {
link = new SingleLinkedList();
}
/** Push element x onto stack. */
public void push(int x) {
link.addFirstNode(x);
link.setSize(link.getSize()+1) ;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
link.deleteFirstNode();
link.setSize(link.getSize()-1);
return link.findNde(1).data;
}
/** Get the top element. */
public int top() {
return link.findNde(1).data;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return link.isEmpty();
}
}
