数据结构之链表及其Java实现_数据结构之单链表的Java实现

Java代码如下：

package com.ds.list;

/**

* 带头结点的单链表

*/

public class LinkedList {

//链表的节点

static class Node {

public int data;

public Node next;

}

//链表头结点

private Node head;

//单链表构造方法

public LinkedList() {

head = new Node();

head.data = 0; //头结点中的数据域存放当前链表的长度

head.next = null;

}

//添加节点

public void add(int data) {

Node p = head;

while(p.next != null) {

p = p.next;

}

Node node = new Node();

node.data = data;

p.next = node;

node.next = null;

head.data += 1;

}

//按节点值删除节点

public boolean remove(int n) {

Node pre = head;

Node cur = head.next;

if(cur == null) {

return false;

}

while(cur != null) {

if(cur.data == n) {

//存在

pre.next = cur.next;

head.data -= 1;

return true;

}else {

cur = cur.next;

pre = pre.next;

}

}

return false;

}

//根据下标值删除节点

public boolean removeByIndex(int index) {

if(index > head.data - 1) {

return false;

}

Node pre = head;

Node cur = head.next;

for(int i = 0; i < index; i++) {

pre = pre.next;

cur = cur.next;

}

pre.next = cur.next;

head.data -= 1;

return true;

}

// 逆置单链表，如果不改变原来的单链表，则可以通过头插法新建单链表，

// 如果可以改变原来的单链表，则可以从第二个节点开始依次遍历，然后用头插法将节点一个个插入到第一个节点的前面

// 通过新建链表实现链表的逆置

public LinkedList reverseList() {

LinkedList list = new LinkedList();

Node newHead = list.getHead();

Node p = this.head.next;

newHead.next = p;

if(p == null) {

return list;

}

newHead.data += 1;

p = p.next;

newHead.next.next = null;

Node pos = newHead.next;

while(p != null) {

Node node = new Node();

node.data = p.data;

newHead.next = node;

node.next = pos;

pos = node;

newHead.data += 1;

p = p.next;

}

return list;

}

//直接修改当前链表的指针达到逆置链表

public void reverseList2() {

Node p = this.head.next;

if(p == null || p.next == null) {

return ;

}

p = p.next;

Node pNext = p.next;

Node tail = this.head.next;

tail.next = null;

while(p != null) {

this.head.next = p;

p.next = tail;

tail = p;

p = pNext;

if(pNext != null) {

pNext = pNext.next;

}

}

}

//获取链表的头结点

public Node getHead() {

return this.head;

}

//链表的长度

public int size() {

return head.data;

}

//遍历显示链表

public void showList() {

Node p = head.next;

for (; p != null; p = p.next) {

System.out.print(String.format("%d ", p.data));

}

System.out.println();

}

}

测试代码如下：

public class Test {

public static void main(String[] args) {

LinkedList list = new LinkedList();

Random random = new Random();

for(int i = 0; i < 8; i++) {

list.add(random.nextInt(10));

}

print("list data:");

list.showList();

print("after reverse, list data:");

list.reverseList2();

list.showList();

int index = 1;

list.removeByIndex(index);

print(String.format("after remove index %d, list data:", index));

list.showList();

}

public static void print(String msg) {

System.out.println(msg);

}

}测试代码的运行结果如下图：