xhao 2019-12-15
一、单链表的概念
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。这组存储单元可以是连续的,也可以是不连续的。
存储单元由两部分组成,数据源和指针,数据源放数据,指针指向下个存储单元。
二、单链表的结构
采用Node实体类类标识,其中data为存储的数据,next为下一个结点的指针。
//链表的实体类 class Node{ public int data; public Node next; public Node(int data) { this.data = data; } }
三、单链表的常见操作
package org.learn.link; public class TestList { public static void main(String[] args) { // TODO Auto-generated method stub MyLinkedLsit mylist = new MyLinkedLsit(); mylist.addNodeH(22); mylist.addNodeH(32); mylist.addNodeH(25); mylist.addNodeH(11); MyLinkedLsit mylist1 = new MyLinkedLsit(); mylist.print(); System.out.println("链表的长度:"+mylist.getLength()); mylist.delete(1); mylist.print(); } } class MyLinkedLsit{ //初始化头结点(不存放具体数据) Node head = new Node(0); //添加结点(尾插法) public void addNodeT(int data) { Node newnode = new Node(data);//生成新结点 Node cur = head;//当前结点 while(cur.next != null) {//找到最后一个结点 cur = cur.next; } cur.next = newnode; } //添加结点(头插法) public void addNodeH(int data) { Node newnode = new Node(data);//生成新结点 Node cur = head;//当前结点 newnode.next = head.next; head.next = newnode; } //获取链表的长度 public int getLength() { int length = 0; Node cur = head.next; while(cur != null) { length++; cur = cur.next; } return length; } //删除第k个结点 public void delete(int k) { if(k<1 || k>getLength()) { System.out.println("待删除的结点不存在"); return; } int i = 1; Node cur = head; while(cur.next != null) { if(i == k) { cur.next = cur.next.next; return; } else { cur = cur.next; i++; } } } //显示结点 public void print() { Node cur = head.next; while(cur != null) { System.out.print(cur.data +" "); cur = cur.next; } System.out.println(); } } //链表结点的实体类 class Node{ int data;//结点数据 Node next;//下一个结点 public Node(int data) { this.data = data; } }