Java数据结构（链表篇）
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
package ch04L&
public class Link {&
&&& // 数据域&&
&&& // 指针域&&
&&& private L&
&&& // 构造函数&&
&&& public Link(long data) {&
&&&&&&& this.data =&
&&& public long getData() {&
&&& public void setData(long data) {&
&&&&&&& this.data =&
&&& public Link getNext() {&
&&& public void setNext(Link next) {&
&&&&&&& this.next =&
package ch04L
public class Link {
&// 数据域
&// 指针域
&private L
&// 构造函数
&public Link(long data) {
&&this.data =
&public long getData() {
&public void setData(long data) {
&&this.data =
&public Link getNext() {
&public void setNext(Link next) {
&&this.next =
测试连接点：
package ch04L&
public class TestLink {&
&&& public static void main(String[] args) {&
&&&&&&& Link link1 = new Link(10);&
&&&&&&& Link link2 = new Link(50);&
&&&&&&& Link link3 = new Link(20);&
&&&&&&& Link link4 = new Link(100);&
&&&&&&& link1.setNext(link2);&
&&&&&&& link2.setNext(link3);&
&&&&&&& link3.setNext(link4);&
&&&&&&& System.out.println(link1.getData());&
&&&&&&& System.out.println(link1.getNext().getData());&
&&&&&&& System.out.println(link1.getNext().getNext().getData());&
&&&&&&& System.out.println(link1.getNext().getNext().getNext().getData());&
package ch04L
public class TestLink {
&public static void main(String[] args) {
&&Link link1 = new Link(10);
&&Link link2 = new Link(50);
&&Link link3 = new Link(20);
&&Link link4 = new Link(100);
&&link1.setNext(link2);
&&link2.setNext(link3);
&&link3.setNext(link4);
&&System.out.println(link1.getData());
&&System.out.println(link1.getNext().getData());
&&System.out.println(link1.getNext().getNext().getData());
&&System.out.println(link1.getNext().getNext().getNext().getData());
package ch04L&
&* 链表：核心思想：链表中只包含一个数据项，即对第一个连接点的引用
&* @author hadoop
public class LinkList {&
&&& private L&
&&& // 插入&&
&&& public void insert(long value){&
&&&&&&& Link link = new Link(value);&
&&&&&&& if(first == null)&
&&&&&&&&&&& first =&
&&&&&&& else{&
&&&&&&&&&&& link.setNext(first);&
&&&&&&&&&&& first =&
&&&&&&& }&
&&& // 打印链表&&
&&& public void display(){&
&&&&&&& Link current =&
&&&&&&& while(current != null){&
&&&&&&&&&&& System.out.print(current.getData() + & &);&
&&&&&&&&&&& current = current.getNext();&
&&&&&&& }&&&&
&&& // 查询链表&&&
&&& public Link find(long key){&
&&&&&&& Link current =&
&&&&&&& while(current.getData() != key){&
&&&&&&&&&&& if(current.getNext() == null)&
&&&&&&&&&&&&&&&&
&&&&&&&&&&& current = current.getNext();&
&&&&&&& }&
&&& // 插入节点到指定位置&&
&&& public void insert(long value, int pos){&
&&&&&&& if(pos == 0)&
&&&&&&&&&&& insert(value);&
&&&&&&& else{&
&&&&&&&&&&& Link current =&
&&&&&&&&&&& for(int i = 0; i & pos - 1; i++)&
&&&&&&&&&&&&&&& current = current.getNext();&
&&&&&&&&&&& Link link = new Link(value);&
&&&&&&&&&&& link.setNext(current.getNext());&
&&&&&&&&&&& current.setNext(link);&
&&&&&&& }&
&&& // 删除节点&&
&&& public void delete(long value){&
&&&&&&& Link current =&
&&&&&&& Link ago =&
&&&&&&& while(current.getData() != value){&
&&&&&&&&&&& if(current.getNext() == null)&
&&&&&&&&&&&&&&&&
&&&&&&&&&&& else{&
&&&&&&&&&&&&&&& ago =&
&&&&&&&&&&&&&&& current = current.getNext();&
&&&&&&&&&&& }&
&&&&&&& }&
&&&&&&& if(current == first)&
&&&&&&&&&&& first = first.getNext();&
&&&&&&& else&
&&&&&&&&&&& ago.setNext(current.getNext());&
package ch04L
&* 链表：核心思想：链表中只包含一个数据项，即对第一个连接点的引用
&* @author hadoop
public class LinkList {
&private L
&public void insert(long value){
&&Link link = new Link(value);
&&if(first == null)
&&&first =
&&&link.setNext(first);
&&&first =
&// 打印链表
&public void display(){
&&Link current =
&&while(current != null){
&&&System.out.print(current.getData() + & &);
&&&current = current.getNext();
&// 查询链表
&public Link find(long key){
&&Link current =
&&while(current.getData() != key){
&&&if(current.getNext() == null)
&&&current = current.getNext();
&// 插入节点到指定位置
&public void insert(long value, int pos){
&&if(pos == 0)
&&&insert(value);
&&&Link current =
&&&for(int i = 0; i & pos - 1; i++)
&&&&current = current.getNext();
&&&Link link = new Link(value);
&&&link.setNext(current.getNext());
&&&current.setNext(link);
&// 删除节点
&public void delete(long value){
&&Link current =
&&Link ago =
&&while(current.getData() != value){
&&&if(current.getNext() == null)
&&&&current = current.getNext();
&&if(current == first)
&&&first = first.getNext();
&&&ago.setNext(current.getNext());
package ch04L&
public class TestLinkList {&
&&& public static void main(String[] args) {&
&&&&&&& LinkList linkList = new LinkList();&
&&&&&&& linkList.insert(20);&
&&&&&&& linkList.insert(80);&
&&&&&&& linkList.insert(40);&
&&&&&&& linkList.insert(60);&
&&&&&&& linkList.display();&
&&&&&&& System.out.println();&
&&&&&&& System.out.println(&找到节点，数据为：& + linkList.find(80).getData());&
&&&&&&& linkList.insert(100, 0);&
&&&&&&& linkList.display();&
&&&&&&& System.out.println();&
&&&&&&& linkList.delete(80);&
&&&&&&& linkList.display();&
package ch04L
public class TestLinkList {
&public static void main(String[] args) {
&&LinkList linkList = new LinkList();
&&linkList.insert(20);
&&linkList.insert(80);
&&linkList.insert(40);
&&linkList.insert(60);
&&linkList.display();
&&System.out.println();
&&System.out.println(&找到节点，数据为：& + linkList.find(80).getData());
&&linkList.insert(100, 0);
&&linkList.display();
&&System.out.println();
&&linkList.delete(80);
&&linkList.display();
比较链表和顺序表：
package ch04L&
import ch01Array.MyA&
public class Test {&
&&& public static void main(String[] args) {&
&&&&&&& // 构造链表&&
&&&&&&& long date1 = System.currentTimeMillis();&
&&&&&&& LinkList linkList = new LinkList();&
&&&&&&& for(int i = 0; i & 1000000; i++)&
&&&&&&&&&&& linkList.insert(i);&
&&&&&&& long date2 = System.currentTimeMillis();&
&&&&&&& System.out.println(date2 - date1);&
&&&&&&& // 构造顺序表&&
&&&&&&& long date3 = System.currentTimeMillis();&
&&&&&&& MyArray myArray = new MyArray(1000000 + 1);&
&&&&&&& for(int i = 0; i & 1000000; i++)&
&&&&&&&&&&& myArray.insert(i);&
&&&&&&& long date4 = System.currentTimeMillis();&
&&&&&&& System.out.println(date4 - date3);&
&&&&&&& // 链表删除&&
&&&&&&& long date5 = System.currentTimeMillis();&
&&&&&&& linkList.delete(60000);&
&&&&&&& long date6 = System.currentTimeMillis();&
&&&&&&& System.out.println(date6 - date5);&
&&&&&&& // 顺序表删除&&
&&&&&&& long date7 = System.currentTimeMillis();&
&&&&&&& myArray.delete(60000);&
&&&&&&& long date8 = System.currentTimeMillis();&
&&&&&&& System.out.println(date8 - date7);&Java、Python中没有指针，怎么实现链表、图等数据结构？ - 知乎523被浏览79316分享邀请回答8添加评论分享收藏感谢收起Java、Python中没有指针，怎么实现链表、图等数据结构？ - 知乎523被浏览79316分享邀请回答# -*- coding: utf-8 -*-
class Node(object):
def __init__(self, datum, next):
self.__datum = datum
self.__next = next
def datum(self):
return self.__datum
def next(self):
return self.__next
@next.setter
def next(self, next):
self.__next = next
class LinkedList(object):
def __init__(self):
self.__head = None
self.__tail = None
def head(self):
return self.__head
def tail(self):
return self.__tail
def purge(self):
self.__head = None
self.__tail = None
def is_empty(self):
return self.__head is None
def append(self, item):
#Generates the node.
datum = Node(item, None)
#For the first node in a linked list, it will change the head.
if self.__head is None:
self.__head = datum
self.__tail.next = datum
self.__tail = datum
def remove(self, item):
pointer = self.__head
prepointer = None
#Finds the item
while pointer and pointer.datum != item:
prepointer = pointer
pointer = pointer.next
#Raise the error when not finding the item.
if pointer is None: raise KeyError
#When the linked list has one node, it will sets the head.
if pointer == self.__head:
self.__head = pointer.next
prepointer.next = pointer.next
if pointer == self.__tail:
self.__tail = prepointer
4添加评论分享收藏感谢收起Java、Python中没有指针，怎么实现链表、图等数据结构？ - 知乎523被浏览79316分享邀请回答112 条评论分享收藏感谢收起